Re: HRT proposal (on top of timeofday and soft-timer rework)

[George Anzinger]

Nishanth Aravamudan wrote:
> George,
>
> Thank you for your thoughtful response. Sorry for the long delay in my
> reply! I hope you have seen my new patch, which tries to accommodate your
> suggestions. I also have some more pseudo code for you! (read the new
> code before replying to my old comments, since most of them no longer
> apply).
>
> On 08.06.2005 [16:10:09 -0700], George Anzinger wrote:
~
> > I am most concerned about MMAX_HRT_REQ.  The HR timer list is an ordered 
> > list and if kept small a simple O(N/2) list structure works fine.  If 
> > MMAX_HRT_REQ get too large, this assumption fails and we will have list 
> > access timing issues. In looking at the structure for this list in the 
> > current patch, I concluded that more complex list structures may have a 
> > lower order but also carry a higher fixed cost.  In other words the access 
> > time is:
> >
> > FIXED_OVERHEAD+O(*)
> >
> > Once you move away from the simple O(N/2) structure into RB trees, for 
> > example, the FIXED_OVERHEAD part of the access time goes up so the pay out 
> > for small N is just not there.  For this reason, we want to keep the HR 
> > timer list small which means, in your case, keeping MMAX_HRT_REQ as small 
> > as possible.
>
>
> I think we have found a reasonable way to avoid the risk of this
> complexity (we being myself, Darren Hart and John Stultz, both of whom I
> much of these ideas to).
>
> OK, here is the new pseudo code, finally! When I refer to
> unchanged/identical code, I mean relative to mainline, not to my
> previous pseudo code.
>
> -----------------------------------------------
>
> struct timer_list
> 	/* keep all existing fields and add ... */
> 	nsec_t expires_nsecs;
>
> #define TIMER_MAGIC		0x4b87ad6e	/* in the existing code */
> #define HRTIMER_MAGIC		0x4b87ad6f	/* added, and now we can mask w/ ...*/
> #define HRTIMER_MAGIC_MASK	0x1		/* added, the only bit
> 						 * different between LR and HR magic
> 						 * fields */
>
> init_hrtimer(timer)
> 	/* identical to init_timer() except ... */
> 	timer->magic = HRTIMER_MAGIC
>
> set_timer_nsecs()
> 	/* identical except ... */
> 	if (timer->magic & HRTIMER_MAGIC_MASK)
> 		notify hr-subsytem that a new hrtimer has been added (if
> 		it's expires is before the next interrupt?)
>
> We will adjust the timer expiration alogrithm as follows (currently this
> is in run_timer_softirq() / __run_timers()). This callback sequence will
> be executed on *both* the low-res and high-res soft-timer interrupt!:
>
> soft_timer_callback:
>   nsec_t now_nsecs = do_monotonic_clock()
>   unsigned long now_timerintervals =
>   	nsecs_to_timerintervals_floor(now_nsecs)
>   __run_timers(base, now_timerintervals) /* catch up *all* timers previous
> 					    to the current interval */
> 				      	/* unless we've missed ticks,
> 					   this will do nothing if this
> 					   is a high-res interrupt */
> 					/* maybe extend this function to
> 					   return the time of the next
> 					   low-res interrupt (VST) */ <<<<<<<<<<<<<<<<<
>   nsec_t next_hrt_interrupt = __run_hrtimers(now_nsecs)
> 						/* alogrithm below */
> 						/* and this should,
> 						   likewise, do nothing
> 						   in the low-res case
> 						 */
>   schedule_hrt_interrupt(next_hrt_interrupt) /* interact with h/w */
>
> Depending on how long soft_timer_callback takes to run, we may actually
> need to put it in a loop, to catch any reprogramming the interrupt
> source to go off right now
>
> __run_hrtimers(nsec_t now_nsecs)
> 	this function *must* be run after __run_timers() with
> 		nsecs_to_timerintervals_floor(now_nsecs), thus
> 		guaranteeing all soft-timers before that converted value
> 		have already been expired
> 	traverse the current bucket of timers, expiring *all* timers
> 		with timer->expires_nsecs < now_nsecs
> 	store the expires_nsecs field of the first high-res timer seen
> 		satisfying timer->expires_nsecs > now_nsecs
> 		if no such timer is found, keep checking up to
> 			HZ_to_timerintervals(2) intervals away from now
> 			(2 ticks is adjustable, I suppose) (anything
> 			further may be too time-consuming / unnecessary)
> 		if a satisfying timer is found, return
> 			timer->expires_nsecs, the next hrt interrupt's
> 			time
> 		if not, return 0 (none found)

This fixes what?  It seems to me that you still have the possibility of time 
inversion between the two.  Also, unless you put the timers in the list in 
sorted order, there may be inversion within the HR group.

Lets step back a few steps...

There are a couple of issues I think need to be explored here.

First is the whole notion of moving away from the jiffie.  For better or worse, 
the jiffie ~= 1/HZ, is visible in user land.  But, and I think, more 
importantly, it is tuned to the hardware in that it is currently defined as the 
best the hardware can do to come up with ticks at a HZ per second rate.  In the 
case where the hardware can not exactly match a 1/HZ rate (as for HZ=1000), the 
jiffie is changed to what the hardware can do.  In your timer list you are 
choosing buckets (apparently) based on the ease of calculation of the interval 
given a nanosecond request.  I have not done the whole conversion overhead 
analisis on this choice (it should be done), but the hard fact is that the timer 
list is processed on interrupt and _should_ be set up to match what the hardware 
can do.

So now the issue of what "low res" resolution is comes up.  Is this resolution 
arbitrary or is it exactly what you are calling a timerinterval?  If I make a 
request for a low res timer that is to repeat at a 1 nanosecond rate, the system 
is to set the repeat rate to the resolution (round up according to the 
standard).  Further, I can read this value either via posix_getres() or by 
timer_gettime() so the resolution is visible from user land.  I don't see any 
thing in your code (as yet) to set this resolution.  In any case, it is a fixed 
number.  It seems to me that you have a choice here of either "timerintervals" 
or "the hardware interrupt rate" or "1/HZ".  If it is any thing other than the 
hardware interrupt rate, the actual expire times will drift around within this 
resolution (what customers call jitter) due to the drifting of the hardware 
interrupt WRT the resolution.

I notice that you are still using the cascade timer list.  This list is ideal 
for then normal timer insert, remove, expire operations.  Even timers that are 
inserted in the cascade area are _usually_ removed prior to being the subject of 
a cascade.  On the other hand, it is a real bear of a list to find the "next" 
timer to expire.  The VST operation, thus, should be reserved for the idle task 
and NOT depend on any thing one does in the normal course of handling timers.

Now, back to your proposal.  What you have is very much like the structure that 
I abandoned early this year, i.e. an integrated HR and LR timer list.  The 
reasons for my moving away from it are that it requires that timers in each 
bucket be ordered, thus what was an O(1) insert becomes O(N/M*2) (where M is the 
number of buckets).  Further, this overhead is done at timer insert time and 
introduces additional overhead even if there are no HR timers in the given 
bucket.  It also adds complexity to both the add_timer and run_timer code.  It 
also does the full run_timer overhead for each HR timer interrupt, said overhead 
possibly being higher than code to _just_ handle a simple HR this period only 
list.  By not ordering the timers until just prior to expire time, most of those 
that will never expire will have been pulled from the list already, thus 
reducing the ordering overhead.  There are also complexity issues around 
requests for a timer that has already expired that I handled better with the 
dual list approach.

I have gotten feedback on both the before and after HRT code with the before 
being negative and the after positive.

Could you remind us of why you are redoing the timers?  What is the objective of 
this?
> ~

--
George Anzinger   george@xxxxxxxxxx
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/