Re: [PATCH 0/5] clocksource patches

[Roman Zippel <zippel@linux-m68k.org>]

Hi,

Below is a first draft of some documentation which hopefully helps to
better understand the clock update function. It tries to introduce the 
various concepts in small logical steps from the basic xtime updates to 
the continuous clocks with full error adjustment.
It's still rather raw, but it contains all the information one has to 
understand to adjust and customize the clock update code.

Feedback welcome. :)

bye, Roman



There are three basic time variables related to time management:

- cycles: managed by the hardware clock
- ntp_time: managed by the NTP system and is updated in regular
  intervals (ticks)
- xtime: local base time as used by gettimeofday

Each variable is regularly updated:

- cycle_update: defines the basic tick frequency and is initialized with
  (frequency / HZ)
- ntp_update: is calculated by the NTP system
- xtime_update: is derived from cycle_update using a conversion factor
  (cycle_update*mult)

gettimeofday uses xtime and the cycle counter to calculate the current
time:

	timeofday = xtime + cycle_offset * mult;

cycle_offset is the offset to the last timer tick and mult is a fixed
point conversion factor from cycles to seconds. mult is initialized
based on the equivalence of 1 sec to frequency cycles:

	1 sec = frequency * mult
	mult = 10^9 nsec / frequency

Time is updated at every tick (after cycle_update cycles), which for a
simple system system looks like this:

	xtime = ntp_time += ntp_update;
	if (xtime.tv_nsec >= NSEC_PER_SEC) {
		ntp_time -= NSEC_PER_SEC;
		xtime.tv_nsec -= NSEC_PER_SEC;
		xtime.tv_sec++;
		second_overflow();
	}

xtime and ntp_time are basically identical, which means at every update
step gettimeofday can jump by a small error value (ntp_update -
xtime_update). To avoid this jump we have to update ntp_time and xtime
separately:

	ntp_time += ntp_update;
	xtime += cycle_update * mult;
	if (xtime.tv_nsec >= NSEC_PER_SEC) {
		ntp_time -= NSEC_PER_SEC;
		xtime.tv_nsec -= NSEC_PER_SEC;
		xtime.tv_sec++;
		second_overflow();
	}
	error = ntp_time - xtime;
	mult_adj = error / cycle_update;
	mult += mult_adj;

This produces an error between ntp_time and xtime and to keep both
synchronized, we have to modify mult (the only other variable in the
timeofday calculation).  mult_adj is the difference between the new and
old multiplier and is derived from:

	cycle_update * mult_new = cycle_update * mult + error

One big problem with this is that we only look at the current error,
which causes the multiplier to oscillate if ntp_update changes (the
adjustments are applied too late), so it's better to look ahead to the
next update:

	ntp_time += ntp_update;
	xtime += cycle_update * mult;
	if (xtime.tv_nsec >= NSEC_PER_SEC) {
		ntp_time -= NSEC_PER_SEC;
		xtime.tv_nsec -= NSEC_PER_SEC;
		xtime.tv_sec++;
		second_overflow();
	}
	error = (ntp_time + ntp_update) - (xtime + cycle_update * mult);
	mult_adj = error / cycle_update;
	mult += mult_adj;

The important thing here is that the error calculation happens after
calling second_overflow(), which is the main callback for the NTP system
to update ntp_update.
Instead of calculating the complete error every time, we can also update
the error incrementally and avoid maintaining ntp_time:

	xtime += cycle_update * mult;
	if (xtime.tv_nsec >= NSEC_PER_SEC) {
		xtime.tv_nsec -= NSEC_PER_SEC;
		xtime.tv_sec++;
		second_overflow();
	}
	error += ntp_update - cycle_update * mult;
	mult_adj = error / cycle_update;
	mult += mult_adj;
	error -= cycle_update * mult_adj;

This is probably the step, which makes the calculation less obvious as
there is no explicit ntp_time anymore and is instead maintained via the
difference to xtime. It's very important to keep in mind that the error
is for the next update step, so if we change the multiplier for the next
tick, we also have to adjust the error:

	cycle_update * mult - cycle_update * mult_new

as at the next step xtime is not advanced by (cycle_update * mult)
anymore but (cycle_update * mult_new) instead.

Note that although we don't maintain the ntp_time value anymore, the
complexity has only shifted to the error calculation, but since under
normal circumstances (clock is synchronized and stable) adjustments to
the multiplier are less common events, the calculation becomes cheaper
with a simple error update and occasional error adjustments.

This is already sufficient for simple systems, but interrupts can delay
the update step, so that we can see small time jumps due to the
multiplier adjustments. To avoid this we have to include the current
cycle_offset into the calculation:

	xtime += cycle_update * mult;
	if (xtime.tv_nsec >= NSEC_PER_SEC) {
		xtime.tv_nsec -= NSEC_PER_SEC;
		xtime.tv_sec++;
		second_overflow();
	}
	error += ntp_update - cycle_update * mult;
	mult_adj = error / cycle_update;
	mult += mult_adj;
	xtime -= cycle_offset * mult_adj;
	error -= (cycle_update - cycle_offset) * mult_adj;

We adjust xtime to keep the current time the same after the multiplier
change:

	xtime_new + cycle_offset * mult_new = xtime + cycle_offset * mult

Since we change xtime, we don't have to forget to also adjust the error
by the same amount.


If the time is now updated in very irregular intervals, it can happen
that we skipped an update step, where we can either just repeat
everything or skip a few error adjustment steps and do them at the end
instead:

	while (cycle_offset >= cycle_update) {
		cycles_last += cycle_update;
		cycle_offset -= cycle_update;
		xtime += cycle_update * mult;
		if (xtime.tv_nsec >= NSEC_PER_SEC) {
			xtime.tv_nsec -= NSEC_PER_SEC;
			xtime.tv_sec++;
			second_overflow();
		}
		error += ntp_update - cycle_update * mult;
	}
	mult_adj = error / cycle_update;
	mult += mult_adj;
	xtime -= cycle_offset * mult_adj;
	error -= (cycle_update - cycle_offset) * mult_adj;



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/