[U-Boot] [RFC] Review of U-Boot timer API

[J. William Campbell]

On 5/22/2011 8:26 PM, Reinhard Meyer wrote:
> Dear J. William Campbell,
>> On 5/22/2011 1:15 AM, Reinhard Meyer wrote:
>>> Dear J. William Campbell,
>>>
>>> please demonstrate for me (and others), by a practical example,
>>> how _any_ arithmetic (even less with just shifts and multiplies)
>>> can convert a free running 3.576 MHz (wild example) free running
>>> 32 bit counter (maybe software extended to 64 bits) into a ms
>>> value that will properly wrap from 2**32-1 to 0 ?
>> Hi All
>> I accept the challenge! I will present two ways to do this, one using 
>> a 32 bit by 16 bit divide, and one using only multiplies.
>> This first method is "exact", in that there is no difference in 
>> performance from a "hardware" counter ticking at the 1 ms rate. This 
>> is accomplished by operating the 1 ms counter based on the delta time 
>> in the hardware time base. It is necessary to call this routine often 
>> enough that the hardware counter does not wrap more than once between 
>> calls. This is not really a problem, as this time is 1201 seconds or 
>> so. If the routine is not called for a long time, or at the first 
>> call, it will return a timer_in_ms value that will work for all 
>> subsequent calls that are within a hardware rollover interval. Since 
>> the timer in ms is a 32 bit number anyway. The same rollover issue 
>> will exist if you "software extend" the timer to 64 bits. You must 
>> assume 1 rollover. If it is more than 1, the timer is wrong.
>>
>>
>> The variables in the gd are
>> u32 prev_timer;
>> u32 timer_in_ms;
>> u16 timer_remainder;
>>
>> /* gd->timer remainder must be initialized to 0 (actually, an number 
>> less than 3576, but 0 is nice). Other two variables don't matter but 
>> can be initialized if desired */
>>
>> u32 get_raw_ms()
>> {
>> u32 delta;
>> u32 t_save;
>>
>> read(t_save); /* atomic read of the hardware 32 bit timer running at 
>> 3.576 MHz */
>> delta_t = (t_save - gd->prev_timer) ;
>>
>> gd->prev_timer = t_save;
>> /*
>> Hopefully, the following two lines only results in one hardware 
>> divide when optimized. If your CPU has no hardware divide, or if it 
>> slow, see second method .
>> */
>> gd->timer_in_ms += delta_t / 3576; /* convert elapsed time to ms */
>> gd->timer_remainder += delta_t % 3576; /* add in remaining part not 
>> included above */
>> if (gd->timer_remainder >= 3576) /* a carry has been detected */
>> {
>> ++gd->timer_in_ms;
>> gd->timer_remainder -= 3576; /* fix remainder for the carry above */
>> }
>>
>> return(gd->timer_in_ms)
>> }
>
> Thank you! Basically this is similar to a Bresenham Algorithm.
Hi All,
       Yes, I think you are correct. I didn't know it by that name, but 
i think you are correct. It is a bit different use of the idea, but it 
is very similar.
>
>>
>> This approach works well when the number of ticks per ms is an exact 
>> number representable as a small integer, as it is in this case. It is 
>> exact with a clock rate of 600 MHz, but is not exact for a clock rate 
>> of 666 MHz. 666667 is not an exact estimate of ticks per ms, It is 
>> off by 0.00005 % That should be acceptable for use as a timeout 
>> delay. The accumulated error in a 10 second delay should be less than 
>> 0.5 ms.
>
> I would think the non exact cases result in such a small error that 
> can be
> tolerated. We are using the ms tick for timeouts, not for providing a 
> clock
> or exact delays. We should just round up when calculating the divider.
Yes, we should round off the divider value, so 666.6666666666 MHz rounds 
to 666667 ticks/Ms while 333.3333333333 MHz rounds to 333333 ticks/Ms.
>
> Hence the hick-ups that result when this is not called frequent enough to
> prevent a multiple rollover of the raw value between calls do not matter
> either (they should be just documented).
Good, I am glad we agree on this also.
>
>>
>> There is a way that the divide above can be approximated by 
>> multiplying by an appropriate fraction, taking the resulting delta t 
>> in ms, multiplying it by 3576, and subtracting the product from the 
>> original delta to get the remainder. This is the way to go if your 
>> CPU divides slowly or not at all. This approach is presented below.
>>
> [...]
>
> Optimizations would be up to the implementer of such a hardware and work
> only if the divider is a compile time constant. Often the divider will be
> run time determined (AT91 for example).
Correct. I will provide a "generic" version that computes the constants 
at run time.  If the clock rate is a constant, these routines can be 
overridden at compile/link time. This generic version should be 
available on Monday for further review.

Best Regards,
Bill Campbell
>
> Reinhard
>
>