I have been studying HPET and wondering why they used the approach they did.. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.

HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.

My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.

robf...@gmail.com wrote:
> I have been studying HPET and wondering why they used the approach they did. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
>
> HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
>
> My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
>

Obviously, a single down counter will be enough if you have a supervisor
that gathers all counting requests:

When a new request comes in, it is compared with the current counter
value and if less, is placed at the front of the queue with the counter
set to this value. At the same time the previous front is decremented by
the new top priority count.

In this way, each event just contains the delta from the previous event,
the only real issue is when things occur so quickly or close together
that you have problems updating the queue, but you can fix this byusing
the free-running counter to measure hw long it took you to update the
down counter. :-)

If you instead have a single free-running counter and a single
comparator the world becomes simpler since you just have to iterate over
queue entries until you find the next which has a deadline which hasn't
already passed while you were processing the previous entry.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Friday, August 12, 2022 at 1:07:38 AM UTC-5, robf...@gmail.com wrote:
> I have been studying HPET and wondering why they used the approach they did.
<
A single constantly incrementing counter is always true to itself.
A single constantly incrementing counter cannot drift with respect to other
counters.

MitchAlsup wrote:
> On Friday, August 12, 2022 at 1:07:38 AM UTC-5, robf...@gmail.com wrote:
>> I have been studying HPET and wondering why they used the approach they did.
> <
> A single constantly incrementing counter is always true to itself.
> A single constantly incrementing counter cannot drift with respect to other
> counters.

It cannot drift WRT other counters driven by the same clock signal.
It certainly can drift WRT external clocks like wall clocks.

Crystals have an inherent inaccuracy which manufacturers binning
(sorting parts into accuracy bins to sell at different prices)
skews results for, plus temperature and aging variations.

The counter bit precision and its increment amount decides your
ability to compensate for the above inaccuracies. How long you
expect a system to run between time adjustments comes into play.

Also, depending on the software design, a multi-shot timer can introduce
drift in the delay between when a timer fires and when it is requeued.
Short duration multi-shot timers can miss a firing deadline if timer
processing gets far enough behind, say because of other interrupts.

You can minimize software drift by having an absolute time counter
and having multi-shot timers automatically requeue themselves for
the next absolute deadline until explicitly stopped.
When the absolute clock >= the oldest timer queue entry, pop/requeue
one or more entries and dispatch each timers' callback routine,
until timer entry deadline is > current clock.

If it is an SMP system you can have a bunch of race conditions
to deal with, as timers can be triggering on one cpu while a
different cpu is trying to cancel that timer.

robf...@gmail.com wrote:
> I have been studying HPET and wondering why they used the approach they did.. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
>
> HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
>
> My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
>

By the way, if you are referring to the High Precision Event Timer HPET
as specified by Intel then a quicky search finds lots of complaints
from both OS implementers and end users, and I see many people looking
for ways to disable it because it has a large jitter
(variable trigger latency) that interferes with games.

Its spec says clock is >= 10 MHz and drift for intervals >= 1 millisecond
is +- 500 ppm. Note that is 500 pmm is 1/2 the millisecond time interval
which, if my calculation is correct, is +- 43.2 seconds per day.

IA-PC HPET (High Precision Event Timers) Specification, 2004
http://www.intel.com/content/dam/www/public/us/en/documents/technical-specifications/software-developers-hpet-spec-1-0a.pdf

"The timers are implemented as a single up-counter with a set of
comparators. The counter increases monotonically. When software does
two consecutive reads of the counter, the second read will never return
a value that is less than the first read unless the counter has actually
rolled over. Each timer includes a match register and a comparator.
Each individual timer can generate an interrupt when the value in its
match register equals the value of the free-running counter.
Some of the timers can be enabled to generate a periodic interrupt."

The see a number of problems:

- the compare register can be either 32 or 64 bits.
This was obviously done so it works with x86 and x64.

However if a 32 bit compare then software has to deal with partial
matches and wraps, and this interacts (badly) with issues below.

It would not have been difficult to have all compare values
be 64-bits and just have x86 write two values, low and high,
with compare disabled on the low write and re-enabled on high write.

- the compare function is == NOT >=
Since it triggers on == you can miss trigger.

At 10 MHz a 64-bit >= compare should not be a problem even for FPGA.
A high performance >= is an XOR with a find-last-set which is a
log_4 parallel prefix NAND, so say 4 or 5 gate delays.

- there is a unknown latency between read of current counter and when
it replies, and a possibly different latency on trigger writes.

That is why the compare == is a problem because OS software
has to correct for all of this, which introduces more jitter.

- even though the internal counters can be up to femtosecond (10^-15 s)
resolution, the timer increment value appears to be read-only so there
is no way to adjust this to compensate for hardware variations.

The specified drift makes this completely unusable as a system clock
base which means a separate hardware and software system for regular
OS timers and "HPET" ones. Which is a good thing as the requirements
for each could be different but thats a different set of API's.

On Saturday, August 13, 2022 at 1:15:33 PM UTC-4, EricP wrote:
> robf...@gmail.com wrote:
> > I have been studying HPET and wondering why they used the approach they did.. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
> >
> > HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed.. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
> >
> > My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
> >
> By the way, if you are referring to the High Precision Event Timer HPET
> as specified by Intel then a quicky search finds lots of complaints
> from both OS implementers and end users, and I see many people looking
> for ways to disable it because it has a large jitter
> (variable trigger latency) that interferes with games.
>
> Its spec says clock is >= 10 MHz and drift for intervals >= 1 millisecond
> is +- 500 ppm. Note that is 500 pmm is 1/2 the millisecond time interval
> which, if my calculation is correct, is +- 43.2 seconds per day.

Yeah, I saw all the posts too, people asking how to disable the timers.
Got the impression they are not well liked.

> IA-PC HPET (High Precision Event Timers) Specification, 2004
> http://www.intel.com/content/dam/www/public/us/en/documents/technical-specifications/software-developers-hpet-spec-1-0a.pdf
>
> "The timers are implemented as a single up-counter with a set of
> comparators. The counter increases monotonically. When software does
> two consecutive reads of the counter, the second read will never return
> a value that is less than the first read unless the counter has actually
> rolled over. Each timer includes a match register and a comparator.
> Each individual timer can generate an interrupt when the value in its
> match register equals the value of the free-running counter.
> Some of the timers can be enabled to generate a periodic interrupt."
>
> The see a number of problems:
>
> - the compare register can be either 32 or 64 bits.
> This was obviously done so it works with x86 and x64.
>
> However if a 32 bit compare then software has to deal with partial
> matches and wraps, and this interacts (badly) with issues below.
>
> It would not have been difficult to have all compare values
> be 64-bits and just have x86 write two values, low and high,
> with compare disabled on the low write and re-enabled on high write.
>
> - the compare function is == NOT >=
> Since it triggers on == you can miss trigger.
>
> At 10 MHz a 64-bit >= compare should not be a problem even for FPGA.
> A high performance >= is an XOR with a find-last-set which is a
> log_4 parallel prefix NAND, so say 4 or 5 gate delays.

So, the comparators should ideally compare ‘>=’? Or possibly an option
for either.

The HPET may use either level or edge sensitive outputs. I wonder if
the ‘==’ comparators are so that the edge outputs are not continuously
triggering. It is just a little bit more logic to track if and edge occurred already.

> - there is a unknown latency between read of current counter and when
> it replies, and a possibly different latency on trigger writes.
>
> That is why the compare == is a problem because OS software
> has to correct for all of this, which introduces more jitter.
>
> - even though the internal counters can be up to femtosecond (10^-15 s)
> resolution, the timer increment value appears to be read-only so there
> is no way to adjust this to compensate for hardware variations.

I do not think it is an increment value in terms of being added to the
counter. The counter just increments by one all the time. The counter
would have to be counting at a THz rate to be adjustable.
I think the idea is the counter will be hard-wired for a fixed oscillator and
its necessary to know the frequency or period. If vendor A uses a 10 Mhz
clock and vendor B uses a 15 MHz one there must be a way to track how
much the counter increments by in terms of femtoseconds. So that the
compare values can be adjusted for the clock frequency.

I found the timer increment value confusing. It shows it as read-only but
later in the document it shows it as read/write and says to be careful
updating it.

> The specified drift makes this completely unusable as a system clock
> base which means a separate hardware and software system for regular
> OS timers and "HPET" ones. Which is a good thing as the requirements
> for each could be different but thats a different set of API's.

I have written my own PET core that uses a single up counter now. I have
the luxury of not worrying about backwards compatibility. It is strictly 64-bit,
but I use just a 48-bit counter and comparators for now to try and conserve
some hardware in the FPGA which is running low on resources. That is still
enough to time events almost a year in duration at 10 MHz. Decided not to
provide FSB interrupt messaging as that would add to the size of the core.

On Saturday, August 13, 2022 at 5:46:11 PM UTC-5, robf...@gmail.com wrote:
> On Saturday, August 13, 2022 at 1:15:33 PM UTC-4, EricP wrote:
> > robf...@gmail.com wrote:

> > - the compare function is == NOT >=
> > Since it triggers on == you can miss trigger.
> >
> > At 10 MHz a 64-bit >= compare should not be a problem even for FPGA.
> > A high performance >= is an XOR with a find-last-set which is a
> > log_4 parallel prefix NAND, so say 4 or 5 gate delays.
<
> So, the comparators should ideally compare ‘>=’? Or possibly an option
> for either.
<
The OS sets the time of the <next> trigger. OS is in charge of the >= part.
<
When the trigger goes off, OS takes everybody off the wait queues
that want to run before the next timer tick. Then schedules the cores
based on priority and affinity of all the runnable threads.

On Saturday, August 13, 2022 at 8:15:33 PM UTC+3, EricP wrote:
>
> Its spec says clock is >= 10 MHz and drift for intervals >= 1 millisecond
> is +- 500 ppm. Note that is 500 pmm is 1/2 the millisecond time interval
> which, if my calculation is correct, is +- 43.2 seconds per day.
>

You'll have hard time buying 500ppm oscillator. They don't appear to be
available at standard places.
You can buy 200ppm or 150ppm oscillator, but it is not clear to me why
would you want to. This low-stability parts are exotic and as such are much
more expensive than "normal" 20 to 100ppm oscillator.

Among "normal" 14.318 MHz, 15pF, CMOS output oscillators there is little
difference in price, at least for moderate quantities. I don't know what
happens when you buy 1M, but for lot of 3000 the common part (25 ppm) appears
to be the cheapest - 0.56 USD on Mouser.

If you want better than 20 ppm then you'd have to pay more, but not a lot more.
10 ppm MEMS oscillators are available in lots of 3000 for 0.98 USD with somewhat
inconvenient 40 pF load capacitance and for 2.16 USD with standard 15 pF capacitance.

robf...@gmail.com wrote:
> On Saturday, August 13, 2022 at 1:15:33 PM UTC-4, EricP wrote:
>> robf...@gmail.com wrote:
>>> I have been studying HPET and wondering why they used the approach they did.. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
>>>
>>> HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed.. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
>>>
>>> My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
>>>
>> By the way, if you are referring to the High Precision Event Timer HPET
>> as specified by Intel then a quicky search finds lots of complaints
>> from both OS implementers and end users, and I see many people looking
>> for ways to disable it because it has a large jitter
>> (variable trigger latency) that interferes with games.
>>
>> Its spec says clock is >= 10 MHz and drift for intervals >= 1 millisecond
>> is +- 500 ppm. Note that is 500 pmm is 1/2 the millisecond time interval
>> which, if my calculation is correct, is +- 43.2 seconds per day.
>
> Yeah, I saw all the posts too, people asking how to disable the timers.
> Got the impression they are not well liked.
>
>> IA-PC HPET (High Precision Event Timers) Specification, 2004
>> http://www.intel.com/content/dam/www/public/us/en/documents/technical-specifications/software-developers-hpet-spec-1-0a.pdf
>>
>> "The timers are implemented as a single up-counter with a set of
>> comparators. The counter increases monotonically. When software does
>> two consecutive reads of the counter, the second read will never return
>> a value that is less than the first read unless the counter has actually
>> rolled over. Each timer includes a match register and a comparator.
>> Each individual timer can generate an interrupt when the value in its
>> match register equals the value of the free-running counter.
>> Some of the timers can be enabled to generate a periodic interrupt."
>>
>> The see a number of problems:
>>
>> - the compare register can be either 32 or 64 bits.
>> This was obviously done so it works with x86 and x64.
>>
>> However if a 32 bit compare then software has to deal with partial
>> matches and wraps, and this interacts (badly) with issues below.
>>
>> It would not have been difficult to have all compare values
>> be 64-bits and just have x86 write two values, low and high,
>> with compare disabled on the low write and re-enabled on high write.
>>
>> - the compare function is == NOT >=
>> Since it triggers on == you can miss trigger.
>>
>> At 10 MHz a 64-bit >= compare should not be a problem even for FPGA.
>> A high performance >= is an XOR with a find-last-set which is a
>> log_4 parallel prefix NAND, so say 4 or 5 gate delays.
>
> So, the comparators should ideally compare ‘>=’? Or possibly an option
> for either.

Yes >=, or decrement the trigger value before storing it and use > as it
is slightly faster (it doesn't need to NOR with the XOR values).

An == would only be need if you wanted compatibility with that spec.

The problem with == is you don't know when the next clock is.
There can be arbitrary delay between read of current timer counter
and write of the trigger due to other interrupts or cache misses.
A short duration could miss its trigger value and then it would wait
until the counter to wrap around. This is not what was wanted
so software has to correct for this, adding more jitter.

The document warns of this:
"WARNING: Software developers must be careful when programming the
comparator registers. If the value written to the register is not
sufficiently set far enough ahead of the current register value,
then the counter may pass the value before it reaches the register
and the interrupt will be missed."

A 64-bit compare > does not have this problem.

> The HPET may use either level or edge sensitive outputs. I wonder if
> the ‘==’ comparators are so that the edge outputs are not continuously
> triggering. It is just a little bit more logic to track if and edge occurred already.

Yes, that is my guess too, they chose == so they can do 32 bit compares
on the low order counter and trigger values, as a compare > on just the
low order 32 bits would incur repeated false triggering.

The correct solution is to require 64 bit compares,
not to do == compares on the low order 32 bits and
then throw software at it to fix the inevitable issues.

There is also a warning that a 64-bit read of the time counter
on a 64-bit cpu might be turned into two 32 bit reads internally
by the HPET hardware and therefore miss a carry-out from low order
to high order 32-bits. This forces software to always read the
counter in a loop until it gets the same value twice.

The correct solution is to require 64 bit reads on 64 bit cpus,
not to maybe allow value tearing along 32 bit boundaries and
expect software to patch it up.

>> - there is a unknown latency between read of current counter and when
>> it replies, and a possibly different latency on trigger writes.
>>
>> That is why the compare == is a problem because OS software
>> has to correct for all of this, which introduces more jitter.
>>
>> - even though the internal counters can be up to femtosecond (10^-15 s)
>> resolution, the timer increment value appears to be read-only so there
>> is no way to adjust this to compensate for hardware variations.
>
> I do not think it is an increment value in terms of being added to the
> counter. The counter just increments by one all the time. The counter
> would have to be counting at a THz rate to be adjustable.
> I think the idea is the counter will be hard-wired for a fixed oscillator and
> its necessary to know the frequency or period. If vendor A uses a 10 Mhz
> clock and vendor B uses a 15 MHz one there must be a way to track how
> much the counter increments by in terms of femtoseconds. So that the
> compare values can be adjusted for the clock frequency.

There looks to be a read-only register COUNTER_CLK_PERIOD that contains
the tick size in femtoseconds. Software would scale delay durations
with that value to get a tick count and then wait for that many ticks.

> I found the timer increment value confusing. It shows it as read-only but
> later in the document it shows it as read/write and says to be careful
> updating it.

I didn't see the read-write value for COUNTER_CLK_PERIOD.

>> The specified drift makes this completely unusable as a system clock
>> base which means a separate hardware and software system for regular
>> OS timers and "HPET" ones. Which is a good thing as the requirements
>> for each could be different but thats a different set of API's.
>
> I have written my own PET core that uses a single up counter now. I have
> the luxury of not worrying about backwards compatibility. It is strictly 64-bit,
> but I use just a 48-bit counter and comparators for now to try and conserve
> some hardware in the FPGA which is running low on resources. That is still
> enough to time events almost a year in duration at 10 MHz. Decided not to
> provide FSB interrupt messaging as that would add to the size of the core.

48 bits is enough for 345 days of 100 nsec ticks before wrap around.
That 48 bit value could be OR'ed with a 16-bit high order value
in memory to produce the full 64 bit counter for software to use.
It might be handy if the timer unit generated a specific interrupt on
carry out from the up counter so it can increment the 16-bit high order
value so software doesn't always have to check for overflow.

The spec is over 20 years old but there is no reason for something
like this to be complicated or inefficient if one considers both
the HW and SW implications during its design.

For example, I haven't looked at how this interacts with the interrupt
subsystem but it should be possible for almost all of the timer register
manipulations to be done without disabling and enabling interrupts,
even on 32-bit cpus.

On 8/11/2022 11:07 PM, robf...@gmail.com wrote:
> I have been studying HPET and wondering why they used the approach they did. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
>
> HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
>
> My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
>

It could be that they were trying to provide the capability to read the
timer, do something, then read it again in order to tell the elapsed
time to do that thing. From what I understand, your implementation
doesn't provide that capability. Is it needed? It depends.

So that brings up a question relevant for comp.arch. What are the
requirements for a timer in a clean sheet design?

Some questions:

I assume the "timing an event" functionality is required, as well as the
"interrupt at a specified time in the future" functionality.

What is the required time granularity?

For the interrupt at a specified time function, how many comparitors are
required. Is one enough? I can see an argument for two, one self
resetting, one not. I don't see much need for more than that.

Should the implementation allow multiple reads of the timer to return
the same value?

How closely should the timer be synched to external time?

How long should it be before the timer rolls over?

Other issues. Discuss. :-)

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Monday, August 15, 2022 at 11:14:50 PM UTC-5, Stephen Fuld wrote:
> On 8/11/2022 11:07 PM, robf...@gmail.com wrote:
> > I have been studying HPET and wondering why they used the approach they did. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
> >
> > HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed.. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
> >
> > My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
> >
> It could be that they were trying to provide the capability to read the
> timer, do something, then read it again in order to tell the elapsed
> time to do that thing. From what I understand, your implementation
> doesn't provide that capability. Is it needed? It depends.
>
> So that brings up a question relevant for comp.arch. What are the
> requirements for a timer in a clean sheet design?
>
> Some questions:
>
> I assume the "timing an event" functionality is required, as well as the
> "interrupt at a specified time in the future" functionality.
>
> What is the required time granularity?
<
No worse than 1ns.
>
> For the interrupt at a specified time function, how many comparitors are
> required. Is one enough? I can see an argument for two, one self
> resetting, one not. I don't see much need for more than that.
<
1 comparator on machines with 10 cycle context switching.
>
> Should the implementation allow multiple reads of the timer to return
> the same value?
<
This defeats the ability to use the timer to sort conflicts.
>
> How closely should the timer be synched to external time?
<
1ns
>
> How long should it be before the timer rolls over?
<
at least a month.
>
> Other issues. Discuss. :-)
>
Constant access time delay.
>
>
>
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

On Tuesday, August 16, 2022 at 12:01:01 PM UTC-4, MitchAlsup wrote:
> On Monday, August 15, 2022 at 11:14:50 PM UTC-5, Stephen Fuld wrote:
> > On 8/11/2022 11:07 PM, robf...@gmail.com wrote:
> > > I have been studying HPET and wondering why they used the approach they did. Is there some value to using just a single counter? The only thing I could think of was power consumption. I may switch my somewhat naïve timer implementation if there is good cause.
> > >
> > > HPET uses a single up counter and comparators and adders to trigger periodic or non-periodic events. It seems to me to be more complex than needed. To determine when the next non-periodic event occurs the current counter value must be added onto then the comparator updated. For periodic events the comparator is automatically increased by the last amount written to the comparator register.
> > >
> > > My timer system is organized more like a classic 8254 or 6840 timer. I used down counters and pre-sets for each timer. The comparator is a compare to zero count to trigger events. The counters can be auto pre-set to get periodic events. There are multiple counters but I think this is no worse than having adders for each timer. It amounts to the same resource usage.
> > >
> > It could be that they were trying to provide the capability to read the
> > timer, do something, then read it again in order to tell the elapsed
> > time to do that thing. From what I understand, your implementation
> > doesn't provide that capability. Is it needed? It depends.
> >
> > So that brings up a question relevant for comp.arch. What are the
> > requirements for a timer in a clean sheet design?
> >
> > Some questions:
> >
> > I assume the "timing an event" functionality is required, as well as the
> > "interrupt at a specified time in the future" functionality.
> >
> > What is the required time granularity?
> <
10 ns or 100 ns, easily achievable in a PLD.

> >
> > For the interrupt at a specified time function, how many comparitors are
> > required. Is one enough? I can see an argument for two, one self
> > resetting, one not. I don't see much need for more than that.
> <

30+ comparators per core (300 comparators?) might allow every
process to have its own comparator. Which would not need to be
managed by the OS.

> >
> > Should the implementation allow multiple reads of the timer to return
> > the same value?
> <
Yes. The software could just loop until it gets the next value if unique values
are needed. If the timer is close to the processor speed, it is not going to
loop very many times. Might be handy to have hardware assistance for this.
Sync to port value change instruction.

> >
> > How closely should the timer be synched to external time?
> <
Should be able to sync to the minimum increment.

> >
> > How long should it be before the timer rolls over?
> <
A year or more. There is lots of work done on weekly or monthly basis.
Some work is done on quarterly or yearly basis - seasonal.

> > Other issues. Discuss. :-)
> >
> >
> >
> > --
> > - Stephen Fuld
> > (e-mail address disguised to prevent spam)

robf...@gmail.com <robfi680@gmail.com> schrieb:

> 30+ comparators per core (300 comparators?) might allow every
> process to have its own comparator. Which would not need to be
> managed by the OS.

Hmm... do you want to restrict the core to 300 processes? Hard
limits have a habit of coming around and biting the user when it
least expected (for example when an attacker or a buggy process
does a few forks() and uses up all of them).

And you would need the OS anyway to schedule access to them so
so it is guaranteed that no two processes use the same timer.

Thomas Koenig wrote:
> robf...@gmail.com <robfi680@gmail.com> schrieb:
>
>> 30+ comparators per core (300 comparators?) might allow every
>> process to have its own comparator. Which would not need to be
>> managed by the OS.
>
> Hmm... do you want to restrict the core to 300 processes? Hard
> limits have a habit of coming around and biting the user when it
> least expected (for example when an attacker or a buggy process
> does a few forks() and uses up all of them).
>
> And you would need the OS anyway to schedule access to them so
> so it is guaranteed that no two processes use the same timer.

You don't need to dedicate a high resolution timer to a process.
That wouldn't do much good as processes can have many timers
and software within a single process won't know about other timers.

Each one-shot HW hr-comparator manages a queue of requests.
The queue can be a linked list or binary tree in ascending order
of absolute timeout hr-tick time. The earliest timeout timestamp
is written into the trigger register, or 0 to disable the trigger
if the queue is empty.

If there are multiple hr-comparators then there are multiple queues.
The OS could distribute new timer inserts across queues.
That allows inserts to do less work as they have to touch
fewer other timer objects in each queue (less cache misses).

I don't see much advantage in allowing a process or thread or
device driver to reserve a timer queue to itself.
And all such software would have to deal with the possibility
that the timer queue reservation request was denied.
This adds complexity without adding value.

On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
> Thomas Koenig wrote:
> > robf...@gmail.com <robf...@gmail.com> schrieb:
> >
> >> 30+ comparators per core (300 comparators?) might allow every
> >> process to have its own comparator. Which would not need to be
> >> managed by the OS.
> >
> > Hmm... do you want to restrict the core to 300 processes? Hard
> > limits have a habit of coming around and biting the user when it
> > least expected (for example when an attacker or a buggy process
> > does a few forks() and uses up all of them).
> >
> > And you would need the OS anyway to schedule access to them so
> > so it is guaranteed that no two processes use the same timer.
<
> You don't need to dedicate a high resolution timer to a process.
> That wouldn't do much good as processes can have many timers
> and software within a single process won't know about other timers.
>
> Each one-shot HW hr-comparator manages a queue of requests.
<
Yes, obviously...
<
> The queue can be a linked list or binary tree in ascending order
> of absolute timeout hr-tick time. The earliest timeout timestamp
> is written into the trigger register, or 0 to disable the trigger
> if the queue is empty.
<
What does SW do in managing this list of event-times when one
event fires, and the next event is 1 tick farther down in time ?
It seems to me that the only way for SW to manage such a queue
would be to have large timer-quanta.
<
>
> If there are multiple hr-comparators then there are multiple queues.
> The OS could distribute new timer inserts across queues.
> That allows inserts to do less work as they have to touch
> fewer other timer objects in each queue (less cache misses).
>
> I don't see much advantage in allowing a process or thread or
> device driver to reserve a timer queue to itself.
> And all such software would have to deal with the possibility
> that the timer queue reservation request was denied.
> This adds complexity without adding value.

MitchAlsup wrote:
> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>> Thomas Koenig wrote:
>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>
>>>> 30+ comparators per core (300 comparators?) might allow every
>>>> process to have its own comparator. Which would not need to be
>>>> managed by the OS.
>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>> limits have a habit of coming around and biting the user when it
>>> least expected (for example when an attacker or a buggy process
>>> does a few forks() and uses up all of them).
>>>
>>> And you would need the OS anyway to schedule access to them so
>>> so it is guaranteed that no two processes use the same timer.
> <
>> You don't need to dedicate a high resolution timer to a process.
>> That wouldn't do much good as processes can have many timers
>> and software within a single process won't know about other timers.
>>
>> Each one-shot HW hr-comparator manages a queue of requests.
> <
> Yes, obviously...

Just making sure everyone is sync'ed on this...

> <
>> The queue can be a linked list or binary tree in ascending order
>> of absolute timeout hr-tick time. The earliest timeout timestamp
>> is written into the trigger register, or 0 to disable the trigger
>> if the queue is empty.
> <
> What does SW do in managing this list of event-times when one
> event fires, and the next event is 1 tick farther down in time ?

Its not just 1 tick as servicing the timers has some latency.
So it a window of N ticks, where N varies depending on cpu load.
That is one of the problems that compare == has,
which is why > or >= should be the trigger compares.
Requeue of periodic timers could encounter this for each trigger.

Periodic timers also have the possibility of multiple timeouts at once.
The timer service routine should loop adding timer duration to the
prior trigger time and counting the number of intervals added,
until the next timeout is in the future.
When the callback routine is called, one of the parameters should
be how many timeouts periods have expired since the last callback.

So to answer your question, it would add 1 or more ticks to the
prior timeout trigger and set that as next future deadline,
which might trigger immediately if the time counter has incremented.
Then call the callback passing (timerPtr, trigCount, arg1, arg2, arg3).

An OS would likely impose a lower limit on the duration of
periodic timers to prevent them taking over the cpu.

Some SMP related software issues:
(a) Can the timer queue(s) be serviced on multiple cpus at once,
or should there be a cpu dedicated to servicing timers?
There is something to be said for each approach.

(b) Can a single timer fire twice in short succession on different
cpus at once, such that you wind up with the same callback routine
for the same timer executing concurrently on multiple cpus?
It is possible to write the timer dispatch software either way.

Timer using software would probably prefer to NOT have to deal with
multiple concurrent timeout firings for the same timer.

> It seems to me that the only way for SW to manage such a queue
> would be to have large timer-quanta.

This is one difference between high resolution timers and
system timers. For system timers a tick size might be 100 ns
but the quanta is defined by OS, such as 1 ms, or 10 ms.

For HR timers the tick size is the quanta defined by the hardware.
Having the model dependent tick size in femtoseconds stored
in a read-only HW register is as good as any method.

Software converts duration specified in, say, nanoseconds to
HR tick counts for that model and waits > that many ticks.

On Wednesday, August 17, 2022 at 12:02:37 PM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
> >> Thomas Koenig wrote:
> >>> robf...@gmail.com <robf...@gmail.com> schrieb:
> >>>
> >>>> 30+ comparators per core (300 comparators?) might allow every
> >>>> process to have its own comparator. Which would not need to be
> >>>> managed by the OS.
> >>> Hmm... do you want to restrict the core to 300 processes? Hard
> >>> limits have a habit of coming around and biting the user when it
> >>> least expected (for example when an attacker or a buggy process
> >>> does a few forks() and uses up all of them).
> >>>
> >>> And you would need the OS anyway to schedule access to them so
> >>> so it is guaranteed that no two processes use the same timer.
> > <
> >> You don't need to dedicate a high resolution timer to a process.
> >> That wouldn't do much good as processes can have many timers
> >> and software within a single process won't know about other timers.
> >>
> >> Each one-shot HW hr-comparator manages a queue of requests.
> > <
> > Yes, obviously...
> Just making sure everyone is sync'ed on this...
> > <
> >> The queue can be a linked list or binary tree in ascending order
> >> of absolute timeout hr-tick time. The earliest timeout timestamp
> >> is written into the trigger register, or 0 to disable the trigger
> >> if the queue is empty.
> > <
> > What does SW do in managing this list of event-times when one
> > event fires, and the next event is 1 tick farther down in time ?
<
> Its not just 1 tick as servicing the timers has some latency.
> So it a window of N ticks, where N varies depending on cpu load.
<
And how much cache+memory interference is present.
<
> That is one of the problems that compare == has,
> which is why > or >= should be the trigger compares.
<
>= is the only thing that makes sense.
<
> Requeue of periodic timers could encounter this for each trigger.
<
With SW in control of queueing and dequeueing, I would have thought
the CPU/core would have an indication of how big N is so that SW
leaves the earliest 'event' in the timer, and everyone between that and
that+N would be dequeued in order of oldness before the SW thinks
the timer event is 'satisfied'.
>
> Periodic timers also have the possibility of multiple timeouts at once.
> The timer service routine should loop adding timer duration to the
> prior trigger time and counting the number of intervals added,
> until the next timeout is in the future.
> When the callback routine is called, one of the parameters should
> be how many timeouts periods have expired since the last callback.
<
This feature should be a part of EVERY asynchronous wakeup system.
"how many of your things happened" before control could be transferred
to you.
>
> So to answer your question, it would add 1 or more ticks to the
> prior timeout trigger and set that as next future deadline,
> which might trigger immediately if the time counter has incremented.
> Then call the callback passing (timerPtr, trigCount, arg1, arg2, arg3).
>
> An OS would likely impose a lower limit on the duration of
> periodic timers to prevent them taking over the cpu.
>
> Some SMP related software issues:
> (a) Can the timer queue(s) be serviced on multiple cpus at once,
> or should there be a cpu dedicated to servicing timers?
> There is something to be said for each approach.
<
I prefer that HW receives the events, and schedules the service routines.
This way, one can service a timer event every 5 CPU cycles (or so);
SW can never be in such a position--and this gets rid of the need for
synchronization, and interrupt latency.
>
> (b) Can a single timer fire twice in short succession on different
> cpus at once, such that you wind up with the same callback routine
> for the same timer executing concurrently on multiple cpus?
<
This question becomes moot if something other than a CPU receives
and processes the event to the point of the context switch(s).
<
> It is possible to write the timer dispatch software either way.
>
> Timer using software would probably prefer to NOT have to deal with
> multiple concurrent timeout firings for the same timer.
<
A single timer "going off" in Sun 10K system was one of the worst possible
things that could happen. Consider: timer goes off, timer dispatcher wakes
up 100+ jobs, IPIs are sent to every CPU, every CPU attempts to dequeue
the front of the highest priority run queue. There were up to 64 CPUs, and
every piece of interference caused N-1 CPUs to have to retry.
<
Nick McLaren said that sometimes it might take a whole second (note not
millisecond or microsecond--a real wall clock second) for all the CPUs to
be running their appointed thread.
<
> > It seems to me that the only way for SW to manage such a queue
> > would be to have large timer-quanta.
> This is one difference between high resolution timers and
> system timers. For system timers a tick size might be 100 ns
> but the quanta is defined by OS, such as 1 ms, or 10 ms.
<
Good point.
>
> For HR timers the tick size is the quanta defined by the hardware.
> Having the model dependent tick size in femtoseconds stored
> in a read-only HW register is as good as any method.
<
Aren't HRTs used more as nanosecond clocks than for scheduling
timer events--that is time measurement rather than scheduling of
events.
>
> Software converts duration specified in, say, nanoseconds to
> HR tick counts for that model and waits > that many ticks.

MitchAlsup wrote:
> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>> Thomas Koenig wrote:
>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>
>>>> 30+ comparators per core (300 comparators?) might allow every
>>>> process to have its own comparator. Which would not need to be
>>>> managed by the OS.
>>>
>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>> limits have a habit of coming around and biting the user when it
>>> least expected (for example when an attacker or a buggy process
>>> does a few forks() and uses up all of them).
>>>
>>> And you would need the OS anyway to schedule access to them so
>>> so it is guaranteed that no two processes use the same timer.
> <
>> You don't need to dedicate a high resolution timer to a process.
>> That wouldn't do much good as processes can have many timers
>> and software within a single process won't know about other timers.
>>
>> Each one-shot HW hr-comparator manages a queue of requests.
> <
> Yes, obviously...
> <
>> The queue can be a linked list or binary tree in ascending order
>> of absolute timeout hr-tick time. The earliest timeout timestamp
>> is written into the trigger register, or 0 to disable the trigger
>> if the queue is empty.
> <
> What does SW do in managing this list of event-times when one
> event fires, and the next event is 1 tick farther down in time ?
> It seems to me that the only way for SW to manage such a queue
> would be to have large timer-quanta.

I think that there are only two ways it can work:

a) Make the comparator >= so that when the next value is written, it
immediately causes a timeout since the tick count has passed. This does
require that comparator to separate between a recent rollower and a long
time to go, typically using 2^63 as the boundary:

diff = next_event_count - current_tick_count;
if ((signed) diff <= 0) fire();

b) Do the same in SW with a polled approach:

When a event count triggers, the handler dispatches it, then grabs the
next count in the queue and inserts it before immediately reading the
current count to check if the time has already passed, if so, handle it
and repeat. The big problem here is of course that there will always be
a tiny window between writing the next comparator value and reading the
current count to check for an overrun. Fixing that adds a lot of hair,
you either need the (HW) ability to get the current count at the same
time as you write the comparator, or some kind of status register to
report on any currently pending timeout.

It is very easy to see why the hw people would prefer a plain ==
comparator, but it does lead to even more issues in software. :-(

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 8/18/2022 12:18 AM, Terje Mathisen wrote:
> MitchAlsup wrote:
>> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>>> Thomas Koenig wrote:
>>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>>
>>>>> 30+ comparators per core (300 comparators?) might allow every
>>>>> process to have its own comparator. Which would not need to be
>>>>> managed by the OS.
>>>>
>>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>>> limits have a habit of coming around and biting the user when it
>>>> least expected (for example when an attacker or a buggy process
>>>> does a few forks() and uses up all of them).
>>>>
>>>> And you would need the OS anyway to schedule access to them so
>>>> so it is guaranteed that no two processes use the same timer.
>> <
>>> You don't need to dedicate a high resolution timer to a process.
>>> That wouldn't do much good as processes can have many timers
>>> and software within a single process won't know about other timers.
>>>
>>> Each one-shot HW hr-comparator manages a queue of requests.
>> <
>> Yes, obviously...
>> <
>>> The queue can be a linked list or binary tree in ascending order
>>> of absolute timeout hr-tick time. The earliest timeout timestamp
>>> is written into the trigger register, or 0 to disable the trigger
>>> if the queue is empty.
>> <
>> What does SW do in managing this list of event-times when one
>> event fires, and the next event is 1 tick farther down in time ?
>> It seems to me that the only way for SW to manage such a queue
>> would be to have large timer-quanta.
>
> I think that there are only two ways it can work:
>
> a) Make the comparator >= so that when the next value is written, it
> immediately causes a timeout since the tick count has passed. This does
> require that comparator to separate between a recent rollower and a long
> time to go, typically using 2^63 as the boundary:
>
>   diff = next_event_count - current_tick_count;
>   if ((signed) diff <= 0) fire();
>
> b) Do the same in SW with a polled approach:
>
> When a event count triggers, the handler dispatches it, then grabs the
> next count in the queue and inserts it before immediately reading the
> current count to check if the time has already passed, if so, handle it
> and repeat. The big problem here is of course that there will always be
> a tiny window between writing the next comparator value and reading the
> current count to check for an overrun. Fixing that adds a lot of hair,
> you either need the (HW) ability to get the current count at the same
> time as you write the comparator, or some kind of status register to
> report on any currently pending timeout.
>
> It is very easy to see why the hw people would prefer a plain ==
> comparator, but it does lead to even more issues in software. :-(

I have seen timers that append a few bit field to the timer. This field
is returned as the low end of the value when one reads the timer. The
contents of this field are incremented each time the timer is read, and
reset to zero each time the timer ticks. The result guarantees a unique
value returned, but does give a value where the bits below the specified
minimum accuracy of the timer may not be accurate.

For example, suppose you have a timer granularity of 1ns, and four bits
in the new field. Someone reading the timer would see a value specified
in 16ths of a ns, but only the bits at or above 1 ns would be accurate.
Thus someone reading the counter will usually get an accurate value (the
extra bits zero), but occasionally it will be off by a small number of
16ths of a nanosecond.

I thought this was an interesting tradeoff.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

On Thursday, August 18, 2022 at 3:18:32 AM UTC-4, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
> >> Thomas Koenig wrote:
> >>> robf...@gmail.com <robf...@gmail.com> schrieb:
> >>>
> >>>> 30+ comparators per core (300 comparators?) might allow every
> >>>> process to have its own comparator. Which would not need to be
> >>>> managed by the OS.
> >>>
> >>> Hmm... do you want to restrict the core to 300 processes? Hard
> >>> limits have a habit of coming around and biting the user when it
> >>> least expected (for example when an attacker or a buggy process
> >>> does a few forks() and uses up all of them).
> >>>
> >>> And you would need the OS anyway to schedule access to them so
> >>> so it is guaranteed that no two processes use the same timer.

With enough timers the process ID could be used to determine which
timer to use, so the OS does not need to schedule one. There are only
about 250 process running on my Windows machine (3,000 threads).
I think a timer component is not very large so there could be a lot of
them.

> > <
> >> You don't need to dedicate a high resolution timer to a process.
> >> That wouldn't do much good as processes can have many timers
> >> and software within a single process won't know about other timers.
> >>
> >> Each one-shot HW hr-comparator manages a queue of requests.
> > <
> > Yes, obviously...
> > <
> >> The queue can be a linked list or binary tree in ascending order
> >> of absolute timeout hr-tick time. The earliest timeout timestamp
> >> is written into the trigger register, or 0 to disable the trigger
> >> if the queue is empty.
> > <
> > What does SW do in managing this list of event-times when one
> > event fires, and the next event is 1 tick farther down in time ?
> > It seems to me that the only way for SW to manage such a queue
> > would be to have large timer-quanta.
> I think that there are only two ways it can work:
>
> a) Make the comparator >= so that when the next value is written, it
> immediately causes a timeout since the tick count has passed. This does
> require that comparator to separate between a recent rollower and a long
> time to go, typically using 2^63 as the boundary:
>
> diff = next_event_count - current_tick_count;
> if ((signed) diff <= 0) fire();
>
> b) Do the same in SW with a polled approach:
>
> When a event count triggers, the handler dispatches it, then grabs the
> next count in the queue and inserts it before immediately reading the
> current count to check if the time has already passed, if so, handle it
> and repeat. The big problem here is of course that there will always be
> a tiny window between writing the next comparator value and reading the
> current count to check for an overrun. Fixing that adds a lot of hair,
> you either need the (HW) ability to get the current count at the same
> time as you write the comparator, or some kind of status register to
> report on any currently pending timeout.
>
> It is very easy to see why the hw people would prefer a plain ==
> comparator, but it does lead to even more issues in software. :-(
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

How about writing the increment amount to the comparator instead
of the absolute value? The current compare value would not need to be
read then. The store operation would just automatically add to the current
count.

What about having two comparator types, one for high precision timing
that works down to ns range and a second type that works on the range
shifted over a number of bits, eight for example, to give a range of value
that can be used to time events into the years? And then use a 72-bit
counter.

On 8/18/2022 8:48 AM, robf...@gmail.com wrote:
> On Thursday, August 18, 2022 at 3:18:32 AM UTC-4, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>>>> Thomas Koenig wrote:
>>>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>>>
>>>>>> 30+ comparators per core (300 comparators?) might allow every
>>>>>> process to have its own comparator. Which would not need to be
>>>>>> managed by the OS.
>>>>>
>>>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>>>> limits have a habit of coming around and biting the user when it
>>>>> least expected (for example when an attacker or a buggy process
>>>>> does a few forks() and uses up all of them).
>>>>>
>>>>> And you would need the OS anyway to schedule access to them so
>>>>> so it is guaranteed that no two processes use the same timer.
>
> With enough timers the process ID could be used to determine which
> timer to use, so the OS does not need to schedule one. There are only
> about 250 process running on my Windows machine (3,000 threads).
> I think a timer component is not very large so there could be a lot of
> them.
>
>>> <
>>>> You don't need to dedicate a high resolution timer to a process.
>>>> That wouldn't do much good as processes can have many timers
>>>> and software within a single process won't know about other timers.
>>>>
>>>> Each one-shot HW hr-comparator manages a queue of requests.
>>> <
>>> Yes, obviously...
>>> <
>>>> The queue can be a linked list or binary tree in ascending order
>>>> of absolute timeout hr-tick time. The earliest timeout timestamp
>>>> is written into the trigger register, or 0 to disable the trigger
>>>> if the queue is empty.
>>> <
>>> What does SW do in managing this list of event-times when one
>>> event fires, and the next event is 1 tick farther down in time ?
>>> It seems to me that the only way for SW to manage such a queue
>>> would be to have large timer-quanta.
>> I think that there are only two ways it can work:
>>
>> a) Make the comparator >= so that when the next value is written, it
>> immediately causes a timeout since the tick count has passed. This does
>> require that comparator to separate between a recent rollower and a long
>> time to go, typically using 2^63 as the boundary:
>>
>> diff = next_event_count - current_tick_count;
>> if ((signed) diff <= 0) fire();
>>
>> b) Do the same in SW with a polled approach:
>>
>> When a event count triggers, the handler dispatches it, then grabs the
>> next count in the queue and inserts it before immediately reading the
>> current count to check if the time has already passed, if so, handle it
>> and repeat. The big problem here is of course that there will always be
>> a tiny window between writing the next comparator value and reading the
>> current count to check for an overrun. Fixing that adds a lot of hair,
>> you either need the (HW) ability to get the current count at the same
>> time as you write the comparator, or some kind of status register to
>> report on any currently pending timeout.
>>
>> It is very easy to see why the hw people would prefer a plain ==
>> comparator, but it does lead to even more issues in software. :-(
>> Terje
>>
>> --
>> - <Terje.Mathisen at tmsw.no>
>> "almost all programming can be viewed as an exercise in caching"
>
> How about writing the increment amount to the comparator instead
> of the absolute value? The current compare value would not need to be
> read then. The store operation would just automatically add to the current
> count.

If you write the increment to the "comparator", you could eliminate the
compare to the clock, by having the hardware decrement the value in the
comparator each time it increments the clock. When the value in the
comparitor hits zero, it "fires".

> What about having two comparator types, one for high precision timing
> that works down to ns range and a second type that works on the range
> shifted over a number of bits, eight for example, to give a range of value
> that can be used to time events into the years? And then use a 72-bit
> counter.

The Unisys 2200 series has a system request that returns the number of
ns since 00:00 Dec 31, 1899, in 72 bits. Of course 72 bits is a lot
easier to handle in a 36 bit word machine. :-) Note: I vaguely recall
it used the trick I mentioned in a previous post such that the accuracy
wasn't 1 ns.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

MitchAlsup wrote:
> On Wednesday, August 17, 2022 at 12:02:37 PM UTC-5, EricP wrote:
>> MitchAlsup wrote:
>>> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>>>> Thomas Koenig wrote:
>>>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>>>
>>>>>> 30+ comparators per core (300 comparators?) might allow every
>>>>>> process to have its own comparator. Which would not need to be
>>>>>> managed by the OS.
>>>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>>>> limits have a habit of coming around and biting the user when it
>>>>> least expected (for example when an attacker or a buggy process
>>>>> does a few forks() and uses up all of them).
>>>>>
>>>>> And you would need the OS anyway to schedule access to them so
>>>>> so it is guaranteed that no two processes use the same timer.
>>> <
>>>> You don't need to dedicate a high resolution timer to a process.
>>>> That wouldn't do much good as processes can have many timers
>>>> and software within a single process won't know about other timers.
>>>>
>>>> Each one-shot HW hr-comparator manages a queue of requests.
>>> <
>>> Yes, obviously...
>> Just making sure everyone is sync'ed on this...
>>> <
>>>> The queue can be a linked list or binary tree in ascending order
>>>> of absolute timeout hr-tick time. The earliest timeout timestamp
>>>> is written into the trigger register, or 0 to disable the trigger
>>>> if the queue is empty.
>>> <
>>> What does SW do in managing this list of event-times when one
>>> event fires, and the next event is 1 tick farther down in time ?
> <
>> Its not just 1 tick as servicing the timers has some latency.
>> So it a window of N ticks, where N varies depending on cpu load.
> <
> And how much cache+memory interference is present.

Yes that affects the actual timer routine performance
but it is independent of the hr timer design.
The design should be such that it is not a bottleneck.

> <
>> That is one of the problems that compare == has,
>> which is why > or >= should be the trigger compares.
> <
> >= is the only thing that makes sense.
> <
>> Requeue of periodic timers could encounter this for each trigger.
> <
> With SW in control of queueing and dequeueing, I would have thought
> the CPU/core would have an indication of how big N is so that SW
> leaves the earliest 'event' in the timer, and everyone between that and
> that+N would be dequeued in order of oldness before the SW thinks
> the timer event is 'satisfied'.

Yes but (a) there is a latency before the timer loop starts and
(b) time continues to pass while the loop is running.
If the clock increment quantum is 1 ms you can ignore these effects but
if it is 1 ns then it can increment before and during timeouts.

The timer queue is guarded by a spinlock which you don't want to hold.
So I would lock queue, read counter, dequeue/requeue one timer at
head of list, release lock, call callback.
Loop doing the above until head of timer queue is > current counter.

If counter increments before, during, or after either the loop will
catch those new expires or it will immediately interrupt again when
a new trigger is set.

>> Periodic timers also have the possibility of multiple timeouts at once.
>> The timer service routine should loop adding timer duration to the
>> prior trigger time and counting the number of intervals added,
>> until the next timeout is in the future.
>> When the callback routine is called, one of the parameters should
>> be how many timeouts periods have expired since the last callback.
> <
> This feature should be a part of EVERY asynchronous wakeup system.
> "how many of your things happened" before control could be transferred
> to you.

It depends on whose code is responsible for requeuing periodic timers.
If auto-requeue is a "feature" of the OS kernel then yes it should.
However it can also be left to individual drivers or apps to requeue
so only those that care would be responsible counting expired intervals.

>> So to answer your question, it would add 1 or more ticks to the
>> prior timeout trigger and set that as next future deadline,
>> which might trigger immediately if the time counter has incremented.
>> Then call the callback passing (timerPtr, trigCount, arg1, arg2, arg3).
>>
>> An OS would likely impose a lower limit on the duration of
>> periodic timers to prevent them taking over the cpu.
>>
>> Some SMP related software issues:
>> (a) Can the timer queue(s) be serviced on multiple cpus at once,
>> or should there be a cpu dedicated to servicing timers?
>> There is something to be said for each approach.
> <
> I prefer that HW receives the events, and schedules the service routines.
> This way, one can service a timer event every 5 CPU cycles (or so);
> SW can never be in such a position--and this gets rid of the need for
> synchronization, and interrupt latency.

On a general purpose cpu I'd just assign one cpu to handle all timers.

But if one has hardware threads then there are multiple ways
timeout events can bind to service threads. There could be:
(a) a single thread triggered by the all timeouts that runs
all timer routines, consecutively.
(b) each timer object is a separate thread that is triggered
to run by its timeout, concurrent by timer request object.
(c) concurrent by individual timeout instance

>> (b) Can a single timer fire twice in short succession on different
>> cpus at once, such that you wind up with the same callback routine
>> for the same timer executing concurrently on multiple cpus?
> <
> This question becomes moot if something other than a CPU receives
> and processes the event to the point of the context switch(s).

These questions are all about when a timeout routine binds to a
HW thread to execute it.

> <
>> It is possible to write the timer dispatch software either way.
>>
>> Timer using software would probably prefer to NOT have to deal with
>> multiple concurrent timeout firings for the same timer.
> <
> A single timer "going off" in Sun 10K system was one of the worst possible
> things that could happen. Consider: timer goes off, timer dispatcher wakes
> up 100+ jobs, IPIs are sent to every CPU, every CPU attempts to dequeue
> the front of the highest priority run queue. There were up to 64 CPUs, and
> every piece of interference caused N-1 CPUs to have to retry.

My impression is that this kind of thing happens for
non-blocking IO polling loops common with sockets.
The solution is for the application to use async IO.

Also for highly contended shared resources like scheduler queues a kernel
should use spin-queues instead of spin-locks to eliminate O(N^2) retries.

> <
> Nick McLaren said that sometimes it might take a whole second (note not
> millisecond or microsecond--a real wall clock second) for all the CPUs to
> be running their appointed thread.
> <
>>> It seems to me that the only way for SW to manage such a queue
>>> would be to have large timer-quanta.
>> This is one difference between high resolution timers and
>> system timers. For system timers a tick size might be 100 ns
>> but the quanta is defined by OS, such as 1 ms, or 10 ms.
> <
> Good point.
>> For HR timers the tick size is the quanta defined by the hardware.
>> Having the model dependent tick size in femtoseconds stored
>> in a read-only HW register is as good as any method.
> <
> Aren't HRTs used more as nanosecond clocks than for scheduling
> timer events--that is time measurement rather than scheduling of
> events.

For general purpose cpus and OS I don't see how anyone could depend on
nanosecond resolution deadlines as there so much variation introduced
by other sources that you will never achieve that actual timing.

By making the hr timer 1 ns or better we ensure that the timer
mechanism is not the performance bottleneck.

On a real-time system where one can lock down cache and one has total
control over all threads and their priorities, maybe those could
nanosecond resolution deadlines could be achieved.

Terje Mathisen wrote:
> MitchAlsup wrote:
>> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>>> Thomas Koenig wrote:
>>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>>
>>>>> 30+ comparators per core (300 comparators?) might allow every
>>>>> process to have its own comparator. Which would not need to be
>>>>> managed by the OS.
>>>>
>>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>>> limits have a habit of coming around and biting the user when it
>>>> least expected (for example when an attacker or a buggy process
>>>> does a few forks() and uses up all of them).
>>>>
>>>> And you would need the OS anyway to schedule access to them so
>>>> so it is guaranteed that no two processes use the same timer.
>> <
>>> You don't need to dedicate a high resolution timer to a process.
>>> That wouldn't do much good as processes can have many timers
>>> and software within a single process won't know about other timers.
>>>
>>> Each one-shot HW hr-comparator manages a queue of requests.
>> <
>> Yes, obviously...
>> <
>>> The queue can be a linked list or binary tree in ascending order
>>> of absolute timeout hr-tick time. The earliest timeout timestamp
>>> is written into the trigger register, or 0 to disable the trigger
>>> if the queue is empty.
>> <
>> What does SW do in managing this list of event-times when one
>> event fires, and the next event is 1 tick farther down in time ?
>> It seems to me that the only way for SW to manage such a queue
>> would be to have large timer-quanta.
>
> I think that there are only two ways it can work:
>
> a) Make the comparator >= so that when the next value is written, it
> immediately causes a timeout since the tick count has passed. This does
> require that comparator to separate between a recent rollower and a long
> time to go, typically using 2^63 as the boundary:
>
> diff = next_event_count - current_tick_count;
> if ((signed) diff <= 0) fire();

Unlike the system clock, the period counter resets to zero at boot.
With a 1 ns tick a 64 bit counter wraps after 584 years of
continuous up-time so it wouldn't need any extra handling.

However if the counter or trigger is smaller, say 32 or 48 bits,
or the ticks smaller, say 1 ps, then the counter wrap generates
an interrupt that increments an epoch number in memory.

The trigger register for the youngest timer at the head of the queue
is only set when the current epoch number >= that timers' epoch.
Otherwise the trigger is disabled.

> b) Do the same in SW with a polled approach:
>
> When a event count triggers, the handler dispatches it, then grabs the
> next count in the queue and inserts it before immediately reading the
> current count to check if the time has already passed, if so, handle it
> and repeat. The big problem here is of course that there will always be
> a tiny window between writing the next comparator value and reading the
> current count to check for an overrun. Fixing that adds a lot of hair,
> you either need the (HW) ability to get the current count at the same
> time as you write the comparator, or some kind of status register to
> report on any currently pending timeout.
>
> It is very easy to see why the hw people would prefer a plain ==
> comparator, but it does lead to even more issues in software. :-(
>
> Terje
>

The original spec also had design options like whether the counter
or comparators were 32 or 64 bits, and if 64 bits are they read and
written atomically or as two separate 32 bit values.
Software had to take all these variations into account.

One of the interactions the Linux folks seemed concerned
about is that an interrupt is generated when the counter wraps,
and this can interact with power state management.
A 32 bit counter with 1 ns resolution tick would overflow every
4 seconds and wake up the processor out of power down.
Another reason to require 64 bit timer components.

robf...@gmail.com wrote:
> On Thursday, August 18, 2022 at 3:18:32 AM UTC-4, Terje Mathisen wrote:
>> MitchAlsup wrote:
>>> On Wednesday, August 17, 2022 at 9:14:55 AM UTC-5, EricP wrote:
>>>> Thomas Koenig wrote:
>>>>> robf...@gmail.com <robf...@gmail.com> schrieb:
>>>>>
>>>>>> 30+ comparators per core (300 comparators?) might allow every
>>>>>> process to have its own comparator. Which would not need to be
>>>>>> managed by the OS.
>>>>> Hmm... do you want to restrict the core to 300 processes? Hard
>>>>> limits have a habit of coming around and biting the user when it
>>>>> least expected (for example when an attacker or a buggy process
>>>>> does a few forks() and uses up all of them).
>>>>>
>>>>> And you would need the OS anyway to schedule access to them so
>>>>> so it is guaranteed that no two processes use the same timer.
>
> With enough timers the process ID could be used to determine which
> timer to use, so the OS does not need to schedule one. There are only
> about 250 process running on my Windows machine (3,000 threads).
> I think a timer component is not very large so there could be a lot of
> them.
>
>>> <
>>>> You don't need to dedicate a high resolution timer to a process.
>>>> That wouldn't do much good as processes can have many timers
>>>> and software within a single process won't know about other timers.
>>>>
>>>> Each one-shot HW hr-comparator manages a queue of requests.
>>> <
>>> Yes, obviously...
>>> <
>>>> The queue can be a linked list or binary tree in ascending order
>>>> of absolute timeout hr-tick time. The earliest timeout timestamp
>>>> is written into the trigger register, or 0 to disable the trigger
>>>> if the queue is empty.
>>> <
>>> What does SW do in managing this list of event-times when one
>>> event fires, and the next event is 1 tick farther down in time ?
>>> It seems to me that the only way for SW to manage such a queue
>>> would be to have large timer-quanta.
>> I think that there are only two ways it can work:
>>
>> a) Make the comparator >= so that when the next value is written, it
>> immediately causes a timeout since the tick count has passed. This does
>> require that comparator to separate between a recent rollower and a long
>> time to go, typically using 2^63 as the boundary:
>>
>> diff = next_event_count - current_tick_count;
>> if ((signed) diff <= 0) fire();
>>
>> b) Do the same in SW with a polled approach:
>>
>> When a event count triggers, the handler dispatches it, then grabs the
>> next count in the queue and inserts it before immediately reading the
>> current count to check if the time has already passed, if so, handle it
>> and repeat. The big problem here is of course that there will always be
>> a tiny window between writing the next comparator value and reading the
>> current count to check for an overrun. Fixing that adds a lot of hair,
>> you either need the (HW) ability to get the current count at the same
>> time as you write the comparator, or some kind of status register to
>> report on any currently pending timeout.
>>
>> It is very easy to see why the hw people would prefer a plain ==
>> comparator, but it does lead to even more issues in software. :-(
>> Terje
>>
>> --
>> - <Terje.Mathisen at tmsw.no>
>> "almost all programming can be viewed as an exercise in caching"
>
> How about writing the increment amount to the comparator instead
> of the absolute value? The current compare value would not need to be
> read then. The store operation would just automatically add to the current
> count.

You would also have to reset the counter to zero.
Remember you also have multiple items in the queue with their
own durations relative to *when they were enqueued/requeued*.

If you work through the software in detail I think you will find
they can accomplish the same but using the offset duration is more work.

> What about having two comparator types, one for high precision timing
> that works down to ns range and a second type that works on the range
> shifted over a number of bits, eight for example, to give a range of value
> that can be used to time events into the years? And then use a 72-bit
> counter.

That is what PC's currently have. The system clock which interrupts
approx 1 to 10 milliseconds and the OS uses that to adjust OS time.
The high resolution timers are in addition to the system clock.

> However if the counter or trigger is smaller, say 32 or 48 bits,
> or the ticks smaller, say 1 ps, then the counter wrap generates
> an interrupt that increments an epoch number in memory.

You'll want to make sure this epoch-interrupt is triggered often enough
to be tested sufficiently to be reliable.

Stefan