Re: Help with the high res timers

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Darren Hart wrote:
George Anzinger wrote:
 |First I want to express my joy that we are discussing these issues at
 some depth.

~
 The point is, the standard, low res, timer code needs to be only
 minimally aware of the HR bits.  On the other hand, since the HR timer
 will be started on expiration of the low res timer, we need that
 expiration to be aligned with the clock in a stable, predictable long
 term way.  (For what its worth, we have yet to address NTP clock
 drifting in the HRT patch, so that is still a fly in this web of time.)


You are still dependent on jiffies which is very unreliable do to lost ticks, HZ vs ACTHZ, etc. Even if you use a periodic tick, it seems the HRT code would still benefit from a human-time soft-timers sub-system that wasn't affected by such things.

Well, first we clean up jiffies WRT lost ticks. We just don't have them with the HRT patch. If you mean being late, just as John's code give the right time all the time so does the HRT time code. The notion is that the TSC or the pm_counter can carry us over a couple of lost ticks as well as the between tick times. So, we aren't affected by lost ticks and ACTHZ just is not part of the POSIX clocks & timers world.


>
~
 For what its worth, we have such a clock in HRT.  It is expressed in
 jiffies and arch_cycles, but jiffies is what is used today as the
 "standard" for internal system time.  This gets into the area of just
 how to express time in areas where you need to quickly get and compare
 the time.  After a lot of though, I decided to use arch_cycles rather
 than nanoseconds because arch_cycles are directly readable from the
 hardware.  Any other unit of time requires a conversion, and, as you
 know, usually requires 64-bits as well.  By staying with arch_cycles we
 avoid "most" of the conversion overhead.


I can see why you might want to use arch_cycles, and at least it is an absolute time. Jiffies though is not. Perhaps HRT could benefit from a conversion to "milliseconds + arch_cycles" ?

Two points here, first, jiffies, once you convince yourself that the PIT is the gold time standard, IS the time. It is the best time we have in the x86 world and in all other archs too. That is what the arch time code is supposed to do. Your milliseconds is, or should be, derived from jiffies or, in other archs, the same place jiffies is derived from, i.e. the time keeping "rock" on the mother board. To account for things like NTP, we always grab arch_cycles, xtime, jiffies, and wall_to_monotonic under a read lock at the same time. This allows us to peg one expression of time against another.

All that said, for HRT to work correctly, the timer must have a high resolution time contained in its structure. Currently this is jiffies and arch_cycles. Further, we need to know that when that jiffies value arrives, we will get called ASAP, and not at some random time between that value and the next time it changes. For repeating timers we use these values _after_ the timer expires to figure the next expire time, so if they are changed by the timer code, we are in trouble.

>
>
~
> I think currently, we do something similar to next_timer_interrupt(),
> making sure we update the stored value whenever we add a new timer, if
> necessary. Except now, we will determine the next time to set the hw
> timer to go off every time we expire timers.


 Finding the next timer is a high overhead operation....

Perhaps it is now, but does it have to be? The process scheduler used to be full of O(N) algorithms to, but they were all converted to O(1) by doing several incremental calculations instead of one huge one. Perhaps something similar could be done with timers by caching a couple of timer expirations and modifying them as timers are added, removed, and modified. Just brainstorming here.

Believe me I did a lot of "brainstorming" around how to keep HR timers along with the LR timers. Until just recently I had a different timer list in timer.c which was hashed on the low timer bits. After much thought and finally realizing that MOST timers do NOT expire, I came to conclude that the current list is just right given what it is currently used for. The stuff that is not O(1) in this structure is the cascading. The reason this is not a big issue is just that most timers are removed prior to the cascade.

In the list structure I used to use, I had to order timers by expire time, accounting for both jiffies and arch_cycles. Now HRT uses the same old cascade structure and the timer code, for the most part, ignores the arch_cycles member. Only on expire is it discovered and the timer sent to the hrtime code where the timer is entered in to a very short list of timers that are to expire some time between now and the next jiffie. This is a very simple O(N/2) list, but it is also really short. (This is a simplified discussion. The code is on the HRT web site and in the HRT CVS on that site for the curious.)


>
~
--
George Anzinger   [email protected]
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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[Index of Archives]     [Kernel Newbies]     [Netfilter]     [Bugtraq]     [Photo]     [Stuff]     [Gimp]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Video 4 Linux]     [Linux for the blind]     [Linux Resources]
  Powered by Linux