How timekeeping works with CONFIG_GENERIC_TIME
========================================================================

The generic timekeeping code maintains and allows access to the systems
understanding of how much time has passed from a certain point. However, in
order to measure the passing of time, the generic timekeeping code relies on
the clocksource abstraction. A clocksource abstracts a free running counter
who's value increases at a known frequency.

In the generic timekeeping code, we use a pointer to a selected clocksource to
measure the passing of time.

struct clocksource *clock

The clocksource has some limitations however. Since its likely of fixed width,
it will not increment forever and will overflow. In order to still properly
keep time, we must occasionally accumulate an interval of time. In the generic
timekeeping code, we accumulate the amount of time system the system booted
into the value system_time, which keeps nanosecond resolution in a ktime_t
storage.

ktime_t system_time

Since its likely your system has not been running continually since midnight on
the 1st of January in 1970, we must provide an offset from that time in
accordance with conventions. This only occasionally changed (via
settimeofday()) offset is the wall_time_offset value, which is also stored as a
ktime_t.

ktime_t wall_time_offset


Since we accumulate time in intervals, we need a base cycle value that we can
use to generate an offset from the time value kept in system_time. We store
this value in cycle_last.

cycle_t cycle_last;


Further since all clocks drift somewhat from each other, we use the adjustment
values provided via adjtimex() to correct our clocksource frequency for each
interval. This frequency adjustment value is stored in ntp_adj.

long ntp_adj;

Now that we've covered the core global variables for timekeeping, lets look at
how we maintain these values.

As stated above, we want to avoid the clocksource from overflowing on us, so we
accumulate a time interval periodically. This periodic accumulation function is
called timeofday_periodic_hook().  In simplified pseudo code, it logically is
presented as:

timeofday_periodic_hook():
	cycle_now = read_clocksource(clock)
	cycle_delta = (cycle_now - cycle_last) & clock->mask
	nsec = cyc2ns(clock, cycle_delta, ntp_adj)
	system_time += nsec
	cycle_last = cycle_now

	/* do other stuff */

You can see we read the cycle value from the clocksource, calculate a cycle
delta for the interval since we last called timeofday_periodic_hook(), convert
that cycle delta to a nanosecond interval (for now ignore ntp_adj), add it to
the system time and finally set our cycle_last value to cycle_now for the next
interval. Using this simple algorithm we can correctly measure and record the
passing of time.

But just storing this info isn't very useful, we also want to make it available
to be used elsewhere. So how do we provide a notion of how much time has passed
inbetween calls to timeofday_periodic_hook()?

First, lets create a function that calculates the time since the last call to
timeofday_peridoic_hook().

get_nsec_offset():
	cycle_now = read_clocksource(clock)
	cycle_delta = (cycle_now - cycle_last) & clock->mask
	nsec = cyc2ns(clock, cycle_delta, ntp_adj)
	return nsec

Here you can see, we read the clocksource, calculate a cycle interval, and
convert that to a nanosecond interval. Just like how it is done in
timeofday_periodic_hook!

Now lets use this function to provide the number of nanoseconds that the system
has been running:

do_monotonic_clock():
	return system_time + get_nsec_offset()

Here we trivially add the nanosecond offset since the last
timeofday_periodic_hook() to the value of system_time which was stored at the
last timeofday_periodic_hook().

Note that since we use the same method to calculate time intervals, assuming
each function is atomic and the clocksource functions as it should, time cannot
go backward!

Now to get the time of day using the standard convention:

do_gettimeofday():
	return do_monotonic_clock() + wall_time_offset

We simply add the wall_time_offset, and we have the number of nanoseconds since
1970 began!


Of course, in real life, things are not so static. We have to handle a number
of dynamic values that may change and affect timekeeping. In order to do these
safely, we must only change values in-between intervals. This means the
periodic_hook call must handle these changes.

Since clocksources can be changed while the system is running, we need to check
for and possibly switch to using new clocksources in the periodic_hook call.
Further, clocksources may change their frequency. Since this must be done only
at a safe point, we use the update_callback function pointer (for more details,
see "How to write a clocksource driver" below), this too must be done
in-between intervals in the periodic_hook call. Finally, since the ntp
adjustment made in the cyc2ns conversion is not static, we need to update the
ntp state machine and get a calculate a new adjustment value.

This adds some extra pseudo code to the timeofday_periodic_hook function:

timeofday_periodic_hook():
	cycle_now = read_clocksource(clock)
	cycle_delta = (cycle_now - cycle_last) & clock->mask
	nsec = cyc2ns(clock, cycle_delta, ntp_adj)
	system_time += nsec
	cycle_last = cycle_now

	next = get_next_clocksource()
	if(next != clock):
		cycle_last = read_clocksource(next)
		clock = next

	if(clock->update_callback):
		clock->update_callback()

	ntp_advance(nsec)
	ppm = ntp_get_ppm_adjustment()
	ntp_adj = ppm_to_mult_adj(clock, ppm)


Unfortunately, the actual timeofday_periodic_hook code is not as simple as this
pseudo code. For performance concerns, much has been done to pre-calculate
values and use them repeatedly. Thus be aware that the code in timeofday.c is
more complex, however the functional logic is the same.


How to port an architecture to GENERIC_TIME
========================================================================
Porting an architecture to the GENERIC_TIME timekeeping code consists of moving
a little bit of code around then deleting a fair amount. It is my hope that
this will reduce the arch specific maintenance work around timekeeping.

Porting an arch usually requires the following steps.

1. Define CONFIG_GENERIC_TIME in the arches Kconfig
2. Implmenting the following functions
	nsec_t read_persistent_clock(void)
	void sync_persistent_clock(struct timespec ts)
3. Removing all of the arch specific timekeeping code
	do_gettimeofday()
	do_settimeofday()
	etc
4. Implementing clocksource drivers
	See "How to write a clocksource driver" for more details

The exeptions to the above are:

5.  If the arch is has no continuous clocksource
	A) Implement 1-3 in the above list.
	B) Define CONFIG_IS_TICK_BASED in arches Kconfig
	C) Implement the "long arch_getoffset(void)" function

6. If the arch supports vsyscall gettimeofday (see x86_64 for reference)
	A) Implement 1-4 in the above list
	B) Define GENERIC_TIME_VSYSCALL
	C) Implement arch_update_vsyscall_gtod()
	D) Implement vsyscall gettimeofday (similar to __get_realtime_clock_ts)
	E) Implement vread functions for supported clocksources



How to write a clocksource driver.
========================================================================
First, a quick summary of what a clocksource driver provides.

Simply put, a clocksource is a abstraction of a free running increasing
counter. The abstraction provides the minimal amount of info for that counter
to be usable for timekeeping. Those required values are:
	1. It's name
	2. A rating value for selection priority
	3. A read function pointer
	4. A mask value for correct twos-complement subtraction
	5. A mult and shift pair that aproximate the counter frequency
		mult/(2^shift) ~= nanoseconds per cycle

Additionally, there are other optionally set values that allow for advanced
functinoality. Those values are:
	6. The update_callback function.
	7. The is_continuous flag.
	8. The vread function pointer
	9. The vdata pointer value


Now lets go over these values in detail.

1. Name.
	The clocksource's name should be unique since it is used for both
identification as well as for manually overriding the default clocksource
selection. The name length must be shorter then 32 characters in order for it
to be properly overrided.

2. Rating value
	This rating value is used as a priority value for clocksource
selection. It has no direct connection to quality or physical properties of the
clocksource, but is to be set and manipulated to guarantee that the best (by no
specific metric) clocksource that will provide correct timekeeping is
automatically selected. Rating suggestions can be found in
include/linux/clocksource.h

3. Read function pointer
	This pointer should point to a function that returns an unsigned
increasing cycle value from the clocksource. The value should have a coverage
from zero to the maximum cycle value the clocksource can provide. This does not
have to be direct hardware value and can also be a software counter. An example
of a software counter is the jiffies clocksource.

4. The mask value
	This value should be the largest power of two that is smaller then the
maximum cycle value. This allows twos complement subtraction to work on
overflow boundary conditions if the max value is less then (cycle_t)-1. So for
example, if we have a 16 bit counter (ie: one that loops to zero after
0x0000FFFF), the mask would be 0xFFFF. So then when finding the cycle
difference around a overflow, where now = 0x0013 and then = 0xFFEE, we can
compute the cycle delta properly using the equation:
	delta = (now - then)&mask
	delta = (0x0013 - 0xFFEE) & 0xFFFF
	delta = 0xFFFF0025 & 0xFFFF  /* note the unmasked negative value */
	delta = 0x25

5. The mult and shift pair
	These 32bit values approximate the nanosecond per cycle frequency of
the clocksource using the equation: mult/(2^shift). If you have a khz or hz
frequency value, the mult value for a given shift value can be easily
calculated using the  clocksource_hz2mult() and clocksource_khz2mult() helper
functions. When selecting a shift value, it is important to be careful. Larger
shift values give a finer precision in the cycle to nanosecond conversion and
allows for more exact NTP adjustments.	However if you select too large a shift
value, the resulting mult value might overflow a cycle_t * mult computation.


So if you have a simple hardware counter that does not change frequency,
filling in the above should be sufficient for a functional clocksource. But
read on for details on implementing a more complex clocksource.

6. The update_callback function pointer.
	If this function pointer is non-NULL, it will be called every periodic
hook when it is safe for the clocksource to change its state. This would be
necessary in the case where the counter frequency changes, for example. One
user of this  function pointer is the TSC clocksource. When the TSC frequency
changes (which may occur if the cpu changes frequency) we need to notify the
clocksource at a safe point where that state may change. Thus, if the TSC has
changed frequency we set the new mult/shift values in the update_callback
function.

7. The is_continuous flag.
	This flag variable (0 if false, 1 if true) denotes that the clocksource
is continuous. This means that it is a purely hardware driven clocksource and
is not dependent on any software code to run for it to increment properly. This
denotation will be useful in the future when timer ticks may be disabled for
long periods of time. Doing so using software clocksources, like the jiffies
clocksource, would cause timekeeping problems.

8. The vread function pointer.
	This function pointer points to a user-space accessible function that
reads the clocksource. This is used in userspace gettimeofday implementations
to improve performance. See the x86-64 TSC clocksource implementation for an
example.

8. The vdata pointer.
	This pointer is passed to the vread function pointer in a userspace
gettimeofday implementation. Its usage is dependent on the vread
implementation, but if the pointer points to data, that data must be readable
from userspace.


Now lets write a quick clocksource for an imaginary bit of hardware. Here are
the specs:

	A 32bit counter can be found at the MMIO address 0xFEEDF000. It runs at
100Mhz. To enable it, the the low bit of the address 0xFEEDF0F0 must be set to
one.

So lets start out an empty cool-counter.c file, and define the clocksource.

#include <linux/clocksource.h>
#include <linux/init.h>
#include <asm/io.h>

#define COOL_READ_PTR	0xFEEDF000
#define COOL_START_PTR	0xFEEDF0F0

static __iomem *cool_ptr = COOL_READ_PTR;

struct clocksource clocksource_cool
{
	.name = "cool",
	.rating = 200,		/* its a pretty decent clock */
	.mask = 0xFFFFFFFF,	/* 32 bits */
	.mult = 0,			/*to be computed */
	.shift = 10,
}


Now let's write the read function:

cycle_t cool_counter_read(void)
{
	cycle_t ret = readl(cool_ptr);
	return ret;
}

Finally, lets write the init function:

void cool_counter_init(void)
{
	__iomem *ptr = COOL_START_PTR;
	u32 val;

	/* start the counter */
	val = readl(ptr);
	val |= 0x1;
	writel(val, ptr);

	/* finish initializing the clocksource */
	clocksource_cool.read = cool_counter_read;
	clocksource_cool.mult = clocksource_khz2mult(100000,
					clocksource_cool.shift);

	/* register the clocksource */
	register_clocksource(&clocksource_cool);
}
module_init(cool_counter_init);


Now wasn't that easy!
