No 100 HZ timer !

Hi,
seems like my first try with the complete patch hasn't made it through to the mailing list. This is the second try with only the common part of the patch. Here we go (again):
---

I have a suggestion that might seem unusual at first but it is important for Linux on S/390. We are facing the problem that we want to start many (> 1000) Linux images on a big S/390 machine. Every image has its own 100 HZ timer on every processor the images uses (normally 1). On a single image system the processor use of the 100 HZ timer is not a big deal but with > 1000 images you need a lot of processing power just to execute the 100 HZ timers. You quickly end up with 100% CPU only for the timer interrupts of otherwise idle images. Therefore I had a go at the timer stuff and now I have a system running without the 100 HZ timer. Unluckly I need to make changes to common code and I want you opinion on it.

The first problem was how to get rid of the jiffies. The solution is simple. I simply defined a macro that calculates the jiffies value from the TOD clock:

  #define jiffies ({ \
          uint64_t __ticks; \
          asm ("STCK %0" : "=m" (__ticks) ); \
          __ticks = (__ticks - init_timer_cc) >> 12; \
          do_div(__ticks, (1000000/HZ)); \
          ((unsigned long) __ticks); \

})
With this define you are independent of the jiffies variable which is no longer needed so I ifdef'ed the definition. There are some places where a local variable is named jiffies. You may not replace these so I renamed them to _jiffies. A kernel compiled with only this change works as always.

The second problem is that you need to be able to find out when the next timer event is due to happen. You'll find a new function "next_timer_event" in the patch which traverses tv1-tv5 and returns the timer_list of the next timer event. It is used in timer_bh to indicate to the backend when the next interrupt should happen. This leads us to the notifier functions. Each time a new timer is added, a timer is modified, or a timer expires the architecture backend needs to reset its timeout value. That is what the "timer_notify" callback is used for. The implementation on S/390 uses the clock comparator and looks like this:
static void s390_timer_notify(unsigned long expires)

  {
          S390_lowcore.timer_event =
                  ((__u64) expires*CLK_TICKS_PER_JIFFY) + init_timer_cc;
          asm volatile ("SCKC %0" : : "m" (S390_lowcore.timer_event));

}
This causes an interrupt on the cpu which executed s390_timer_notify after "expires" has passed. That means that timer events are spread over the cpus in the system. Modified or deleted timer events do not cause a deletion notification. A cpu might be errornously interrupted to early because of a timer event that has been modified or deleted. But that doesn't do any harm,
it is just unnecessary work.

There is a second callback "itimer_notify" that is used to get the per process timers right. We use the cpu timer for this purpose:
void set_cpu_timer(void)

  {
          unsigned long min_ticks;
          __u64 time_slice;
          if (current->pid != 0 && current->need_resched == 0) {
                  min_ticks = current->counter;
                  if (current->it_prof_value != 0 &&
                      current->it_prof_value < min_ticks)
                          min_ticks = current->it_prof_value;
                  if (current->it_virt_value != 0 &&
                      current->it_virt_value < min_ticks)
                          min_ticks = current->it_virt_value;
                  time_slice = (__u64) min_ticks*CLK_TICKS_PER_JIFFY;
                  asm volatile ("spt %0" : : "m" (time_slice));
          }

}
The cpu timer is a one shot timer that interrupts after the specified amount
of time has passed. Not a 100% accurate because VM can schedule the virtual processor before the "spt" has been done but good enough for per process timers.

The remaining changes to common code parts deal with the problem that many ticks may be accounted at once. For example without the 100 HZ timer it is possible that a process runs for half a second in user space. With the next interrupt all the ticks between the last update and the interrupt have to be added to the tick counters. This is why update_wall_time and do_it_prof have changed and update_process_times2 has been introduced.

That leaves three problems: 1) you need to check on every system entry if a tick or more has passed and do the update if necessary, 2) you need to keep track of the elapsed time in user space and in kernel space and 3) you need to check tq_timer every time the system is left and setup a timer event for the next timer tick if there is work to do on the timer queue. These three problems are related and have to be implemented architecture dependent. A nice thing we get for free is that the user/kernel elapsed time
measurement gets much more accurate.

The number of interrupts in an idle system due to timer activity drops from from 100 per second on every cpu to about 5-6 on all (!) cpus if this patch is used. Exactly what we want to have.

All this new timer code is only used if the config option CONFIG_NO_HZ_TIMER
is set. Without it everything works as always, especially for architectures that will not use it.

Now what do you think?

(See attached file: timer_common)

blue skies,
Martin

Linux/390 Design & Development, IBM Deutschland Entwicklung GmbH Schönaicherstr. 220, D-71032 Böblingen, Telefon: 49 - (0)7031 - 16-2247
E-Mail: [email protected]

This is going to be a problem for UML as well, and I was considering something very similar. I did a quick scan of your prose, and the description sounds like what I had in mind.

So, count me in as a supporter of this.

A small request: Since S/390 is not the only port that needs this, I'd be happy if it was made as generic as possible (and it may already be, I haven't gone through the code yet).

Jeff

this is one of linux biggest weaknesses. the fixed interval timer is a throwback. it should be replaced with a variable interval timer with interrupts on demand for any system with a cpu sane/modern enough to have an on-chip interrupting decrementer. (i.e just about any modern chip)

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

Its worth doing even on the ancient x86 boards with the PIT. It does require some driver changes since

	while(time_before(jiffies, we_explode))
		poll_things();

no longer works

It would be great if this could be one of the 2.5 goals/projects.

it would make all sorts of fun and useful timed event services easier to implement and provide (potentially) microsecond resolution as opposed to the current 10Ms.

plus, we would only get one "sysclock" timer interrupt per process quantum instead of 10.

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

Note that programming the PIT is sloooooooow and doing it on every timer add_timer/del_timer would be a pain.

Mikulas

You only have to do it occasionally.

When you add a timer newer than the current one
(arguably newer by at least 1/2*HZ sec)
When you finish running the timers at an interval and the new interval is significantly larger than the current one.

Remember each tick we poke the PIT anyway

That's only if we want to do no better than the current system. We'd want a new variable called timer_margin or something, which would be dependent on interrupt source and processor, and could be tuned up or down via sysctl.

Make that larger or smaller. If we come out of a quiescent state (1 hz interrupts, say) and start getting 10ms timers, we want to respond to them right away.

We could also have a HZ_max tunable above which we would not try to reprogram the interval. On older systems, this could be set at 100-200HZ...

--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Reprogramming takes 3-4 times as long. However, I still agree it's a good idea.

RTAI will run the 8254 timer in one-shot mode if you ask it to. However, on machines without a monotonically increasing counter, i.e., the TSC, you have to use 8254 timer 0 as both the timebase and the interval counter -- you end up slowly losing time because of the race condition between reading the timer and writing a new interval. RTAI's solution is to disable kd_mksound and use timer 2 as a poor man's TSC. If either of those is too big of a price, it may suffice to report that the timer granularity on 486's is 10 ms.

It would be nice to see any redesign in this area make it more modular. I have hardware that would make it possible to slave the Linux system clock directly off a high-accuracy timebase, which would be super-useful for some applications. I've been doing some of this already, both as a kernel patch and as part of RTAI; search for 'timekeeper' in the LKML archives if interested.

dave...

Adding and removing timers happens much more frequently than PIT tick, so comparing these times is pointless.

If you have some device and timer protecting it from lockup on buggy hardware, you actually

send request to device
add timer

receive interrupt and read reply
remove timer

With the curent timer semantics, the cost of add timer and del timer is nearly zero. If you had to reprogram the PIT on each request and reply, it would slow things down.

Note that you call mod_timer also on each packet received - and in worst case (which may happen), you end up reprogramming the PIT on each packet.

Mikulas

This just indicates that the interface needs to be richer -- i.e., such as having a "lazy timer" that means: "wake me up when _at least_ N ns have elapsed, but there's no hurry." If waking you up at N ns is expensive, then the wakeup is delayed until something else interesting happens.

This is effectively what we have now anyway. Perhaps the current add_timer() should be mapped to lazy timers.

dave...

BTW. Why we need to redesign timers at all? The cost of timer interrupt each 1/100 second is nearly zero (1000 instances on S/390 VM is not common case - it is not reasonable to degradate performance of timers because of this).

Timers more precise than 100HZ aren't probably needed - as MIN_RTO is 0.2s and MIN_DELACK is 0.04s, TCP would hardly benefit from them.

Mikulas

well, I can think dozens of real time applications off the top of my head that need beter than 1ms timing resolution (think sensor fusion) 1000 clock interrupts/sec is wasteful when what you need is 1 very precisely timed interrupt.

why do we redesign anything? to make it better. TCP is not the only thing in the system.

if you are in love with the existing system, it shouldn't be hard to make it a config option.

There are a considerable number of people who really do need 1Khz resolution. Midi is one of the example cases. That doesn't mean we have to go to a 1KHz timer, we may want to combine a 100Hz timer with a smart switch to 1Khz

As somebody who is now debating how to measure latencies in a giga-bit ethernet environment with several components doing L3 switching in much less than 10 micro-seconds ... (hardware) I agree that some method is need to achieve higher resolutions. (Sigh... I will likely need to buy something big and expensive) {this is for a system to make use of L. Yarrow's little protocol}

Use Alteon/Netgear cards, everyone else seems to be :-) We get measurements on the order of 100ns, if we are just measuring network latencies. (Data is not transferred over the PCI bus).

-- Jamie

On networking bandwidth shaping and traffic control generally need higher precision timers. There are also people who don't like the minimum 10ms delay for non-busy wait, it's apparently a problem for some apps.

-Andi

Indeed, using precise timers for TCP would probably degrade performance -- you should process a group of timer events together, when resolution is not that important.

There are plenty of apps that need higher resolution. Software modem comes to mind (guess why ;), though the device driver supplies the high resolution timed interrupts in that case.

Games would like to be able to page flip at vertical refresh time -- <1ms accuracy please. Network traffic shaping benefits from better than 1ms timing. Video players want to display their frames preferably without 10ms jitter.

Even that old classic game "snake" benefits from decent timing. I worked on an X multiplayer snake implementation which was very unpleasant and jerky at first. 1. Disable nagle for X connection :-) Better but still jerky. 2. Write delay loop like this:

     calculate next_event_time
     select (0, 0, 0, next_event_time - 20ms)
     while (gettimeofday() < next_event_time)
       /* Busy loop for last 20ms. */

It's no coincidence that I've had to write another very similar event loop recently. You can see, this sort of thing is a real waste of CPU.

-- Jamie

This is an X issue. I was talking with Jim Gettys about what is needed to get the relevant existing X extensions for this working

I've already proposed my /dev/vbi device (currently works only for MGA card)
- read returns when VBI occures - works quite well... (currently in avifile CVS tree)

Anyway in good all days AmigaOS had interrupt service where devices where sending timer request - they were queued and timer device was serving
them in order - I don't see the reason why we should implement this differently.
If there is no real reason to interrupt system more then 100Hz periodicity
then this is ok - scheduler will simple send time request for rescheduling in 10ms.

Why we should create 1KHz timers or so when this way seems to be much more
elegant and will work even on XXGHz systems.

bye

[email protected]

Last time I looked at XF86DGA (years ago), it seemed to have the right hooks in place. Just a matter of server implementation. My recollection is dusty though.

-- Jamie

There is also a timing extension for synchronizing events to happenings. The stopper is the kernel interface for the vblank handling since the irq must be handled and cleared in kernel context before we return to X. We now think we know how to handle that cleanly

Alan

This is the sort of thing that Linux does with slab, dentry, inode caches and so on. In theory the memory is reclaimed as required :-)

It's not a big issue with timers, as the timer elements are fixed size structures that tend to be embedded in other structures. So the lifetime of the timer element is the same as the lifetime of the object associated with the timer.

-- Jamie

Except for cards which don't generate an irq on vsync but do let you see how the raster is proceeding. (I vaguely recall these). For which a PLL and, wait for it.... high resolution timer is needed.

Perhaps that's a 1990s problem that doesn't need a 2000s solution though :-)

-- Jamie

I think it would be wrong if we could not add new very usable features to the system just because some old hardware doesn't support it. (I also believe this was the original idea why XFree has no user interface
for such important thing like VBI screen switch - because not all device could provide such information)
I think those who use such old system probably don't need any synchronized
video or game output - simply because it will not work in such system anyway :)
so we should not worry about this.

[email protected]

s/old/crappy/ -- even old hardware can handle vsync IRQs fine. E.g. TVGA
8900C.

+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: [email protected], PGP key available        +

Think of the original 64k and 256k VGA cards. I think some of those didn't have an irq, but did have a way to read the progress of the raster, which you could PLL to using timer interrupts. Some video games still look fine at 320x200 :-)

-- Jamie

The *original* VGA, i.e. the PS/2 one, did have an IRQ, IIRC (according
to docs -- I haven't ever seen one). Cheap clones might have lacked it, though.

Then there is workstation (non-PC) hardware from early '90s which we run
on and which uses an IRQ-driven interface to graphics adapters -- not only for vsync.

+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: [email protected], PGP key available        +

Just for your information we have a project going that is trying to come up with a good solution for all of this:

http://sourceforge.net/projects/high-res-timers

We have a mailing list there where we have discussed much of the same stuff. The mailing list archives are available at sourceforge.

Lets separate this into findings and tentative conclusions :)

Findings:

a) The University of Kansas and others have done a lot of work here.

b) High resolution timer events can be had with or without changing HZ.

c) High resolution timer events can be had with or without eliminating the 1/HZ tick.

d) The organization of the timer list should reflect the existence of the 1/HZ tick or not. The current structure is not optimal for a "tick less" implementation. Better would be strict expire order with indexes to "interesting times".

e) The current organization of the timer list generates a hiccup every 2.56 seconds to handle "cascading". Hiccups are bad.

f) As noted, the account timers (task user/system times) would be much more accurate with the tick less approach. The cost is added code in both the system call and the schedule path.

Tentative conclusions:

Currently we feel that the tick less approach is not acceptable due to (f). We felt that this added code would NOT be welcome AND would, in a reasonably active system, have much higher overhead than any savings in not having a tick. Also (d) implies a list organization that will, at the very least, be harder to understand. (We have some thoughts here, but abandoned the effort because of (f).) We are, of course, open to discussion on this issue and all others related to the project objectives.

We would reorganize the current timer list structure to eliminate the cascade (e) and to add higher resolution entries. The higher resolution entries would carry an addition word which would be the fraction of a jiffie that needs to be added to the jiffie value for the timer. This fraction would be in units defined by the platform to best suit the sub jiffie interrupt generation code. Each of the timer lists would then be ordered by time based on this sub jiffie value. In addition, in order to eliminate the cascade, each timer list would carry all timers for times that expire on the (jiffie mod (size of list)). Thus, with the current 256 first order lists, all timers with the same (jiffies & 255) would be in the same list, again in expire order. We also think that the list size should be configurable to some power of two. Again we welcome discussion of these issues.

George

f does not imply tick-less is not acceptable, it implies that better process time accounting is not acceptable.

list organization is not complex, it is a sorted absolute time list. I would argue that this is a hell of a lot easier to understand that ticks + offsets.

still, better process time accounting should be a compile CONFIG option, not ignored and ruled out because some one thinks that is is to expensive in the general case.

the whole point of linux and CONFIG options is to get you the kernel with the features you want, not what someone else wants.

there should be a whole range of config options associated with this issue:

CONFIG_JIFFIES == old jiffies implementation
CONFIG_TICKLESS == tickless
CONFIG_HYBRID == old jiffies plus a tickless high-res timer system on
the side but not assoc w/ process and global
timekeeping

CONFIG_USELESS_PROCESS_TIME_ACCOUNTING = old style, cheap time acctg CONFIG_USEFUL_BUT_COSTS_TIME_ACCOUNTING = accurate but expensive time accounting

this way, users who want tickless and lousy time acctg can have it AND people who want jiffies and good time acctg could have it.

these features are largely disjoint and easily seperable. it is also relatively trivial to do this in such a way that drivers depending on the jiffie abstraction can be supported without modification no matter what the configuration.

Mark Salisbury

My thinking is that a timer implementation that forced (f) would have problems gaining acceptance (even with me :). I think a tick less system does force this and this is why we have, at least for the moment, abandoned it. In no way does this preclude (f) as it is compatible with either ticks or tick less time keeping. On the other hand, the stated project objectives do not include (f) unless, of course we do a tick less time system.

The complexity comes in when you want to maintain indexes into the list for quick insertion of new timers. To get the current insert performance, for example, you would need pointers to (at least) each of the next 256 centasecond boundaries in the list. But the list ages, so these pointers need to be continually updated. The thought I had was to update needed pointers (and only those needed) each time an insert was done and a needed pointer was found to be missing or stale. Still it adds complexity that the static structure used now doesn't have.

As I said above, we are not ruling it out, but rather, we are not requiring it by going tick less.

As I said, it is not clear how you could get CONFIG_USELESS_PROCESS_TIME_ACCOUNTING unless you did a tick every jiffie. What did you have in mind?

For the most part, I agree. I am not sure that it makes a lot of sense to mix some of these options, however. I think it comes down to the question of benefit vs cost. If keeping an old version around that is not any faster or more efficient in any way would seem too costly to me. We would like to provide a system that is better in every way and thus eliminate the need to keep the old one around. We could leave it in as a compile option so folks would have a fall back, I suppose.

An Issue no one has raised is that the tick less system would need to start a timer each time it scheduled a task. This would lead to either slow but very precise time slicing or about what we have today with more schedule overhead.

George

a

in

process time

would

offsets.

actually, I think a head and tail pointer would be sufficient for most cases. (most new timers are either going to be a new head of list or a new tail, i.e. long duration timeouts that will never be serviced or short duration timers that are going to go off "real soon now (tm)") the oddball cases would be mostly coming from user-space, i.e. nanosleep which a longerr list insertion disapears in the block/wakeup/context switch overhead

not

the

time accounting can be limited to the quantum expiration and voluntary yields in the tickless/useless case.

I agree that some combinations don't make much sense _TO_ME_ but that doesn't mean they don't meet sombody's needs.

in my case (embedded, medium hard real time, massively parallel multicomputer) the only choices that makes sense to my customers is tickless/useless in deployment and tickless/useful in development/profiling/optimization.

in other cases ticked/useless makes sense (dumb old slow chips)

I have no idea who would want ticked/useful or hybrid. i suggested hybrid as an alternative in case linus might be reluctant to gutting and replacing the sysclock.

no. you would re-use the timer with a new expiration time and a re-insert.

also re overhead. the cost of servicing 10 times as many interrupts as necessary for system function must cost a fair chunk.

I suspect you might go for ticked if its overhead was less. The thing that makes me think the overhead is high for tick less is the accounting and time slice stuff. This has to be handled each system call and each schedule call. These happen WAY more often than ticks... Contrary wise, I would go for tick less if its overhead is the same or less under a reasonable load. Of course, we would also want to check overload sensitivity.

The issue is not the timer structure itself, but the insert and removal time AND the time accounting that would have to go on around it. The timer would need to be computed and started each time on the way out of schedule and stopped and the residue saved on schedule entry. One might want to roll this into the accounting time stuff...

On a half way loaded system? Do you think it is that high? I sort of think that, once the system is loaded, there would be a useful timer tick most of the time. Might be useful to do some measurements of this.

George

A pointer-based priority queue is really not a very complex thing, and there are ways to optimise them for typical cases like the above.

-- Jamie

Please do enlighten me. The big problem in my mind is that the pointers, pointing at points in time, are perishable.

George

Um, I'm not sure what perishability has to do with anything. Timers at the moment can be added, deleted and destroyed and it's no big deal.

Look in an algorithms book under "priority queue". They usually don't say how to use a heap-ordered tree -- usually it's an array -- but you can use a tree if you want. In such a tree, each timer has a link to _two_ next timers and one previous timer. (The previous timer link is only needed if you can delete timers before they expire, which is required for Linux).

I'm not saying saying a heap-ordered tree is fastest. But it's ok, and doesn't require any more storage than the `struct timer' objects themselves.

It's possible to optimise this kind of data structure rather a lot, depending on how you want to use it. Linux' current timer algorithm is a pretty good example of a priority queue optimised for timer ticks, where you don't mind doing a small amount of work per tick.

One notable complication with the kernel is that we don't want every timer to run at its exactly allocated time, except for some special timers. For example, if you have 100 TCP streams and their retransmission times are scheduled for 1.0000s, 1.0001s, 1.0002s, etc., you'd much rather just process them all at once as is done at the moment by the 100Hz timer. This is because cache locality is much more important for TCP retransmits than transmit timing resolution.

There's literature online about this class of problems: look up "event set" and "simulation" and "fast priority queue".

enjoy,
-- Jamie

I bumped into a funny non-optimization a few years ago. A system with a timer queue like the above had been "optimized" by keeping old timer elements... ready for new tasks to link onto and activate. The granularity was 1 millsecond. Over time, all timer values from 0 to roughly 10 minutes had been used. That resulted in 60,000 permanent storage fragments laying about... a significant fragmentation problem. The end was a forced recycle every month or so.

john alvord

as I said, i think the process time accounting is disjoint from the ticked/tickless issue and should therefore be considered seperately..

in my experience with the tickless method, after all pending timers have been serviced, then to determine the interval until the next interrupt should be generated all that is needed is one 64 bit subtraction and a register load (about 5 - 8 cycles)

I think we should spend some serious time with some quick and dirty prototypes of both methods, both to characterize all the issues raised and to refine our ideas when it comes time to implement this.

I also think that we should give some thought to implementing both an improved ticked system and a tickless system to be chosen as CONFIG options so that the developer putting together a system can make a choice based on their needs, and not our whims. I am more than willing to concede that there is a class of customer to whom a ticked system is appropriate, but I am quite sure that there is a class for whom the ticked model is completely unacceptable.

any non-useful tick takes away cycles that could be better used performing FFT's

there are many kinds of loads, some which generate large numbers of timed events and some that generate none or few.
I think we want to be able to provide good solutions for both cases even.

we should do lots of measurements.

Mark

I have just posted a patch on sourceforge:
http://sourceforge.net/projects/high-res-timers

to the 2.4.7 kernel with both ticked and tick less options, switch able at any time via a /proc interface. The system is instrumented with Andrew Mortons time pegs with a couple of enhancements so you can easily see your clock/ timer overhead (thanks Andrew).

Please take a look at this system and let me know if a tick less system is worth further effort.

The testing I have done seems to indicate a lower overhead on a lightly loaded system, about the same overhead with some load, and much more overhead with a heavy load. To me this seems like the wrong thing to do. We would like as nearly a flat overhead to load curve as we can get and the ticked system seems to be much better in this regard. Still there may be applications where this works.

comments? RESULTS?

George

Hi!

Why? Higher overhead is a price for better precision timers. If you rounded all times in "tickless" mode, you'd get about same overhead, right?
Pavel

Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt,
details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.

No. It is not the data structure. I did not change it for the experimental code. This, of course, could lead to some additional overhead looking up the next timer to figure when the next interrupt is needed. I used the code from the IBM tick less patch which did a brute force search. In actual fact this is not too bad as I also force a timer every second, so at most ten lists need to be examined. The instrumentation on this look up hardly shows up, and of course, it is only needed after an interrupt.

The overhead comes from setting up a timer for the "slice" on every schedule. Schedule(), in a busy system, gets called often, and "slices" do not often expire. The other issue is additional overhead for the jiffie (which is a function). On review of this code, I see that it needs to protect it self from interrupt, so as written in the experimental code, it is wrong and could loose track of time (however, it is faster as written). Now neither of these operations take very long, it is just that they are called every schedule, which is called often enough to make a difference. Those who optimized the scheduler with gotos and such knew what they were doing! It is a function that is called enough to make the optimization worth while.

For those who would like to try the experimental system it can be found at:
http://sourceforge.net/projects/high-res-timers
where it is called the "no HZ tick test". Do read the release notes to understand what you are getting.

George

What Pavel says is true only if the data structure for holding pending timers degrades into good O(1) insertion & deletion time in the tickless case.

I recall George Anzinger saying something about the current ticked scheduler being able to insert timers that never reach expiry very efficiently (simply a list insert + delete), whereas the current tickless code could not do that.

Is that right? Is it the data structure that is taking too long to process, when many timers that do not reach expiry are inserted? There would be one such insertion and deletion on every context switch, right?

-- Jamie

all POSIX timer and timer like functions (timer_xxx, nanosleep, alarm etc) are defined to operate on a 'no earlier than' semantic. i.e. if you ask to nanosleep for 500 nsec, you will sleep for no less than 500 nanoseconds, but possibly up to 20,000,500 nanoseconds. this is because the maximum legal POSIX time resolution is 20,000,000 nanoseconds (1/50th second or 50hz because of european electricity and old hardware)

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

actually, I have an algorithm to fix that. (had to implement this on a system with a single 32 bit decrementer (an ADI21060 SHARC, YUK!)) the algorithm simulates a free spinning 64 bit incrementer given a 32 bit interrupting decrementer under exclusive control of the timekeeping code. it also takes into account the read/calculate/write interval.

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

Just for the record, Michael Barabanov did this in RTLinux from before kd_mksound was a function pointer in 1995. Michael had an optimization attempt using channel 1 for a while, but on very slow machines this was not sufficient and he went back to channel 2. Of course, the fundamental problem is that board designers keep putting an 1920s part in machines built in 2001.

Here's the comment from the RTLinux 0.5 patch -- all available on the archives on rtlinux.com.

+/* The main procedure; resets the 8254 timer to generate an interrupt. The
+ * tricky part is to keep the global time while reprogramming it. We latch
+ * counters 0 and 2 atomically before and after reprogramming to figure it out.
+ */

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
 www.fsmlabs.com  www.rtlinux.com

jiffies could be replaced easily enough w/ a macro such as

#define jiffies (get_time_in_jiffies())

then driver code would not need to be touched.

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

Just how would you do kernel/user CPU time accounting then ? It's currently done on every timer tick, and doing it less often would make it useless.

-Andi

On the contrary doing it less often but at the right time massively improves its accuracy. You do it on reschedule. An rdtsc instruction is cheap and all of a sudden you have nearly cycle accurate accounting

Alan

Does not sound very attractive all at all on non virtual machines (I see the point on UML/VM):
making system entry/context switch/interrupts slower, making add_timer slower, just to process a few less timer interrupts. That's like robbing the fast paths for a slow path.

-Andi

Measure the number of clocks executing a timer interrupt. rdtsc is fast. Now consider the fact that out of this you get KHz or better scheduling resolution required for games and midi. I'd say it looks good. I agree the accounting of user/system time needs care to avoid slowing down syscall paths

Alan

the system I implemented this in went from 25 Millisecond resolution to 25-60 Nanosecond resolution (depending on the CPU underneath). that is a theoretical factor of 500,000 to 1,000,000 improvement in resolution for timed events, and the clock overhead after the change was about the same. (+-10% depending on underlying CPU)

this is on a system that only had one clock tick per process quantum, as opposed to the 10 in linux.

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

And measure the number of cycles a gigahertz CPU can do between a 1ms timer. And then check how often the typical application executes something like gettimeofday.

It's also all interrupts, not only syscalls, and also context switch if you want to be accurate.

On modern PC hardware it might be possible to do user/system accounting using performance MSRs. They have a bit in the performance counter that allows to only account user or system. If you find a count that is near equivalent to the cycles you have both: total = rdtsc, user = msr, system = rdtsc-msr. At least PPro derived have event 0x16, number of instructions executed, which might be good enough when multiplied with a factor if your instruction mix is not too unusual.

Still even with that the more complex checking in add_timer doesn't look too good.

-Andi

We dont need to be that accurate. Our sample rate is currently so low the data is worthless anyway

Just without checking on context switch you would lose the information of per pid system/user/total that is currently collected completely.

-Andi

When this is rewritten, I would strongly suggest that we find a way to make 'gettimeofday' nearly free. Certain applications need to use this frequently while still being portable. One solution when you do have clock ticks is a read-only mapped Int. Another cheap solution is library assembly that adds a cycle clock delta since last system call to a 'gettimeofday' value set on every system call return.

sdw

...

sdw

[email protected]  http://sdw.st
Stephen D. Williams
43392 Wayside Cir,Ashburn,VA 20147-4622 703-724-0118W 703-995-0407Fax 
Dec2000

The upcoming x86-64 port supports vsyscalls for just that purpose.

-Andi

Hi!

Except for machines with very slow timers we really should account time to processes during context switch instead of sampling on timer ticks. The current values are in many situations (i.e., lots of processes or a process frequently waiting for events bound to timer) a pile of random numbers.

Have a nice fortnight

Martin `MJ' Mares <[email protected]> <[email protected]> http://atrey.karlin.mff.cuni.cz/~mj/
We all live in a yellow subroutine...

Linux should maintain some sort of per-process decaying average. This data is required for a Unix98-compliant ps program. (for %CPU) Currently ps is using total CPU usage over the life of the process.

which kind of U/K accaounting are you referring to?

are you referring to global changes in world time? are you referring to time used by a process?

I think the reduction of clock interrupts by a factor of 10 would buy us some performance margin that could be traded for a slightly more complex handler.

/*------------------------------------------------**
**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **
**------------------------------------------------*/

yup. however, there is a performance penalty even on fast machines for the fine grained process time usage accounting, and it in the past there has been a strong reluctance to add overhead to syscalls and other context switches.

It would probably be a good compile config option to allow fine or coarse process time accounting, that leaves the choice to the person setting up the system to make the choice based on their needs.

--
/*------------------------------------------------**

**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **

**------------------------------------------------*/

The later.

It depends on your workload if you can trade that in. e.g. when a few hundred TCP sockets are active a lot of timer ticks will run some timer handler. Also generally the kernel has quite a lot of timers. There is some reduction on a idle system. That is no doubt useful for VM/UML/VMware where you can have idle sessions hanging around, but otherwise it's not very interesting to optimize idle systems (except maybe for power saving purposes)

-Andi

are these generaly of the long interval, failure timeout type? i.e. 5 second device timeouts that are killed before they get executed because the device didn't timeout? if so, they have no effect on the number of timer interrupts because they generally never get hit. and when they do, you have to pay the price anyway.

--
/*------------------------------------------------**

**   Mark Salisbury | Mercury Computer Systems    **
**   [email protected]     | System OS - Kernel Team     **
**------------------------------------------------**
**  I will be riding in the Multiple Sclerosis    **
**  Great Mass Getaway, a 150 mile bike ride from **
**  Boston to Provincetown.  Last year I raised   **
**  over $1200.  This year I would like to beat   **
**  that.  If you would like to contribute,       **
**  please contact me.                            **

**------------------------------------------------*/

A lot of them are, but not all.

-Andi

I suggested this a while ago during a discussion about performance measurement. This would be fairly easy to implement using the patch provided with the Linux Trace Toolkit since all entry points and exit points are known (and it already is available in post-mortem analysis). Implementing the measurement code within the kernel should be fairly easy to implement and it would be provided as part of the compile option. All in all, given the measurements I made, I'd place the overhead at around 1% for the computations. (The overhead is very likely to be negligeable when eventual fixes are taken into account.)

===================================================
Karim Yaghmour
[email protected]
Embedded and Real-Time Linux Expert
===================================================