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

[Graeme Russ]

Hi All,

OK, here goes - A much more in-depth generic analysis for a timer API

I hope this highlights why the current discussion thread has ended
up where is has

Regards,

Graeme

Definitions:
 'register' - A storage element - Can be:
   - A dedicated CPU register
   - A location in memory (as defined by a C variable for example)
   - A memory mapped storage location
   - A port-mapped storage location
   - etc

 'platform' - A complete hardware configuration which is capable of
   running U-Boot. An operation performed by 'the plaform' (such as
   incrementing a counter) is assumed to occur without software
   intervention (although initial setup and configuration may be
   required)

 'fixed' - Same across all platforms

 'constant' - Does not change between any two pre-determined events. For
   example 'between power up and power down', 'after being configured to
   the next time it is configured'

 'tick' - A constant period of time - The tick period is not fixed (see
   'fixed' above)

 'counter' - A register which increments by 1 in response to a given
   stimulus (an interupt, a programmed clock, a user pressing a button,
   a character recieved on a serial port etc)

 'tick counter' - A register which is incremented every tick (typically
   by the platform)

 'timer' - A register which stores a value representing a number of
   fixed time intervals (1ms unless otherwise noted)

 'ISR' - Interrupt Service Routine - A function which is called by the CPU
   in response to an interrupt

 'interrupt' - A asynchronous signal which causes the CPU to suspent the
   current flow of program execution and execute an ISR - Upon completion
   of the ISR, control is returned to the suspended program flow

Assumptions:
 - Every platform has a tick counter
 - Not all platforms support interrupts
 - The size of the tick counter is not fixed

Mandatory Platform Requirements:
 - A tick counter MUST exist
 - ticks MUST occur at least once every one millisecond
 - A means of reading the tick counter register MUST be provided
 - A means of obtaining the tick frequency MUST be provided
 - The tick counter MUST be unsigned
 - The tick counter MUST use the entire range of the tick counter register
   (i.e. from 'All 0's' to 'All 1's')
 - The tick counter MUST overflow from "all 1's" to "all 0's"

Goal:
 - Maintain a 1ms time base which can be obtained via a simple call to
   get_timer()
 - The timer MUST use the entire range of it's register (i.e. from
   'All 0's' to 'All 1's')
 - The timer MUST overflow from "all 1's" to "all 0's"
 - Reduce the amount of code duplication between platforms

So what do we need in order to implement a good[1] timer API?
 1. A tick counter
 2. If #1 does not have a period of 1ms, a prescaler to convert
    the tick counter to a 1ms timer
 3. If #2 is a software implementation, a way of regularly calling
    the prescaler

Lets look at each of these in detail:

The tick counter
----------------
There are a wide variety of implementations which can be divided into two
categories:
 Hardware Counters:
 - A non-programmable read-only hardware counter. An example is a simple
   hardware counter that is tick'd by the CPU clock starting at zero when
   the platform is powered-up
 - A non-programmable read-only hardware counter that can be reset to zero
   by writting to a control register
 - A non-programmable hardware counter which can be reset to any arbitrary
   value
 - A programmable hardware counter - Examples include:
   - A prescaler which increments the counter every 'x' CPU clocks where
     'x' is set programatically by writing to reserved control registers
   - A programmable clock source independent of the CPU clock

 Software Counters:
 - Implemented in U-Boot software (C or assembler)
 - Must be regularly triggered (usually by an interrupt)
 - Interrupt period can be programmable (arch/x86/cpu/sc520 has a good
   example) or non-programmable

If the period of the hardware counter or the interrupt generator can be
programmed to 1ms (or is fixed at 1ms) then there is no need to implement
#2 (or, therefore, #3)

Here is a list of some typical tick counter rollover durations. The
following intervals have been rounded down to the nearest whole number and
therefore represent a realistic minimum interval at which the tick counter
must be read to prevent timing glitches caused by multiple roll-overs.

 - 1ms (1kHz), 16-bit - 65 seconds
 - 1ms (1kHz), 32-bit - 49 days
 - 1ms (1kHz), 64-bit - 584,942,417 years
 - 1us (1MHz), 32-bit - 71 minutes
 - 1us (1MHz), 64-bit - 584,942 years
 - 1ns (1GHz), 32-bit - 4 seconds
 - 1ns (1GHz), 64-bit - 584 years

The Prescaler
-------------
The prescaler converts the tick counter (with period <1ms) to a timer with
period = 1ms. As with the tick counter, the prescaler may be implemented
in either hardware or software. Where the prescaler is implemented in
hardware (and provides a 1ms counter) there is no need to implement a
software prescaler. However, if no hardware prescaler exists (or the
hardware presaler does not increase the counter period to 1ms) a software
prescaler is required.

Currently, any required software prescaler is implented per-platform. We
now have a function (thanks Bill Campbell) which implements a software
prescaler by periodically reading the tick counter. This function MUST be
called more frequently that the roll-over period of the tick counter
provided. This function has a few 'nice' features:

 - It can be implemented in /lib/ thus elliminating a lot of platform
   specific implementations
 - It does not require the tick frequency to be known at compile time
 - Is not effected by roll-over of the tick-counter
 - Does not need to be called at contanst rate (only needs to be within
   the rollover period listed above)
 - Optionally does not use divides for platforms where divides are either
   slow or non-exitent
 - Optionally handles a tick period which is not an integer multiple of
   1ms

Regularly Servicing the Software Prescaler
------------------------------------------
If the prescaler is implemented in software, it must be called often
enough to avoid tiemr glitches due to multiple rollovers of the tick
counter between prescaler calls. There are several ways this can be
achieved:
 - Inside get_timer() - Taking into consideration the roll-over periods
   listed earlier (and the fact the common scenario is implementing
   time-outs in the order of a few seconds or so) this may not be such a
   bad approach on most platforms. Any platform with a 64-bit tick
   counter will be fine. Even a 32-bit 1us tick counter could be OK
   (when would we ever need to measure a 71 minute period?). Actually,
   this method should always be used to ensure the timer is up-to-date
   get_timer() returns the current timer value.
 - An ISR - If the platform supports interrupts. Because get_timer() calls
   the prescaler as well, the ISR only needs to be triggered once every
   tick rollover period (actually, slightly quicker to account for ISR
   latency)
 - Main Loop - Last resort option - Breaks when calling stand-alone
   applications such as burn-in test beds etc.


So, provided the platform can provide a tick counter, and the tick counter
can be serviced regularly[2], we can implement a timer API for which the
platform can COMPLETELY disregard the fact that a 1ms time base is
required[3].

[1]An implementation with minimal code duplication across platforms and
   requires as little design and implementation per platform as
   practicalibly possible
[2]During the interval over which a timing operation is being actively
   performed. It does not matter if the timer 'glitches' while it is not
   in use.
[3]Well not quite - The platform does need to make sure the tick period is
   less than 1ms