t/time-test.c

/*
 * Carry out arithmetic to explore conversion of CPU clock ticks to nsec
 *
 * When we use the CPU clock for timing, we do the following:
 *
 * 1) Calibrate the CPU clock to relate the frequency of CPU clock ticks
 *    to actual time.
 *
 *    Using gettimeofday() or clock_gettime(), count how many CPU clock
 *    ticks occur per usec
 *
 * 2) Calculate conversion factors so that we can ultimately convert
 *    from clocks ticks to nsec with
 *      nsec = (ticks * clock_mult) >> clock_shift
 *
 *    This is equivalent to
 *	nsec = ticks * (MULTIPLIER / cycles_per_nsec) / MULTIPLIER
 *    where
 *	clock_mult = MULTIPLIER / cycles_per_nsec
 *      MULTIPLIER = 2^clock_shift
 *
 *    It would be simpler to just calculate nsec = ticks / cycles_per_nsec,
 *    but all of this is necessary because of rounding when calculating
 *    cycles_per_nsec. With a 3.0GHz CPU, cycles_per_nsec would simply
 *    be 3. But with a 3.33GHz CPU or a 4.5GHz CPU, the fractional
 *    portion is lost with integer arithmetic.
 *
 *    This multiply and shift calculation also has a performance benefit
 *    as multiplication and bit shift operations are faster than integer
 *    division.
 *
 * 3) Dynamically determine clock_shift and clock_mult at run time based
 *    on MAX_CLOCK_SEC and cycles_per_usec. MAX_CLOCK_SEC is the maximum
 *    duration for which the conversion will be valid.
 *
 *    The primary constraint is that (ticks * clock_mult) must not overflow
 *    when ticks is at its maximum value.
 *
 *    So we have
 *	max_ticks = MAX_CLOCK_SEC * 1000000000 * cycles_per_nsec
 *	max_ticks * clock_mult <= ULLONG_MAX
 *	max_ticks * MULTIPLIER / cycles_per_nsec <= ULLONG_MAX
 *      MULTIPLIER <= ULLONG_MAX * cycles_per_nsec / max_ticks
 *
 *    Then choose the largest clock_shift that satisfies
 *	2^clock_shift <= ULLONG_MAX * cycles_per_nsec / max_ticks
 *
 *    Finally calculate the appropriate clock_mult associated with clock_shift
 *	clock_mult = 2^clock_shift / cycles_per_nsec
 *
 * 4) In the code below we have cycles_per_usec and use
 *	cycles_per_nsec = cycles_per_usec / 1000
 *
 *
 * The code below implements 4 clock tick to nsec conversion strategies
 *
 *   i) 64-bit arithmetic for the (ticks * clock_mult) product with the
 *	conversion valid for at most MAX_CLOCK_SEC
 *
 *  ii) NOT IMPLEMENTED Use 64-bit integers to emulate 128-bit multiplication
 *	for the (ticks * clock_mult) product
 *
 * iii) 64-bit arithmetic with clock ticks to nsec conversion occurring in
 *	two stages. The first stage counts the number of discrete, large chunks
 *	of time that have elapsed. To this is added the time represented by
 *	the remaining clock ticks. The advantage of this strategy is better
 *	accuracy because the (ticks * clock_mult) product used for final
 *	fractional chunk
 *
 *  iv) 64-bit arithmetic with the clock ticks to nsec conversion occuring in
 *	two stages. This is carried out using locks to update the number of
 *	large time chunks (MAX_CLOCK_SEC_2STAGE) that have elapsed.
 *
 *   v) 128-bit arithmetic used for the clock ticks to nsec conversion.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include <stdlib.h>
#include "lib/seqlock.h"

#define DEBUG 0
#define MAX_CLOCK_SEC 365*24*60*60ULL
#define MAX_CLOCK_SEC_2STAGE 60*60ULL
#define dprintf(...) if (DEBUG) { printf(__VA_ARGS__); }

enum {
	__CLOCK64_BIT		= 1 << 0,
	__CLOCK128_BIT		= 1 << 1,
	__CLOCK_MULT_SHIFT	= 1 << 2,
	__CLOCK_EMULATE_128	= 1 << 3,
	__CLOCK_2STAGE		= 1 << 4,
	__CLOCK_LOCK		= 1 << 5,

	CLOCK64_MULT_SHIFT	= __CLOCK64_BIT | __CLOCK_MULT_SHIFT,
	CLOCK64_EMULATE_128	= __CLOCK64_BIT | __CLOCK_EMULATE_128,
	CLOCK64_2STAGE		= __CLOCK64_BIT | __CLOCK_2STAGE,
	CLOCK64_LOCK		= __CLOCK64_BIT | __CLOCK_LOCK,
	CLOCK128_MULT_SHIFT	= __CLOCK128_BIT | __CLOCK_MULT_SHIFT,
};

static struct seqlock clock_seqlock;
static unsigned long long cycles_start;
static unsigned long long elapsed_nsec;

static unsigned int max_cycles_shift;
static unsigned long long max_cycles_mask;
static unsigned long long nsecs_for_max_cycles;

static unsigned int clock_shift;
static unsigned long long clock_mult;

static unsigned long long *nsecs;
static unsigned long long clock_mult64_128[2];
static __uint128_t clock_mult128;

/*
 * Functions for carrying out 128-bit
 * arithmetic using 64-bit integers
 *
 * 128-bit integers are stored as
 * arrays of two 64-bit integers
 *
 * Ordering is little endian
 *
 * a[0] has the less significant bits
 * a[1] has the more significant bits
 *
 * NOT FULLY IMPLEMENTED
 */
static void do_mult(unsigned long long a[2], unsigned long long b,
		    unsigned long long product[2])
{
	product[0] = product[1] = 0;
	return;
}

static void do_div(unsigned long long a[2], unsigned long long b,
		   unsigned long long c[2])
{
	return;
}

static void do_shift64(unsigned long long a[2], unsigned int count)
{
	a[0] = a[1] >> (count-64);
	a[1] = 0;
}

static void do_shift(unsigned long long a[2], unsigned int count)
{
	if (count > 64)
		do_shift64(a, count);
	else {
		while (count--) {
			a[0] >>= 1;
			a[0] |= a[1] << 63;
			a[1] >>= 1;
		}
	}
}

static void update_clock(unsigned long long t)
{
	write_seqlock_begin(&clock_seqlock);
	elapsed_nsec = (t >> max_cycles_shift) * nsecs_for_max_cycles;
	cycles_start = t & ~max_cycles_mask;
	write_seqlock_end(&clock_seqlock);
}

static unsigned long long _get_nsec(int mode, unsigned long long t)
{
	switch(mode) {
	case CLOCK64_MULT_SHIFT:
		return (t * clock_mult) >> clock_shift;
	case CLOCK64_EMULATE_128: {
		unsigned long long product[2] =  { };

		do_mult(clock_mult64_128, t, product);
		do_shift(product, clock_shift);
		return product[0];
		}
	case CLOCK64_2STAGE: {
		unsigned long long multiples, nsec;

		multiples = t >> max_cycles_shift;
		dprintf("multiples=%llu\n", multiples);
		nsec = multiples * nsecs_for_max_cycles;
		nsec += ((t & max_cycles_mask) * clock_mult) >> clock_shift;
		return nsec;
		}
	case CLOCK64_LOCK: {
		unsigned int seq;
		unsigned long long nsec;

		do {
			seq = read_seqlock_begin(&clock_seqlock);
			nsec = elapsed_nsec;
			nsec += ((t - cycles_start) * clock_mult) >> clock_shift;
		} while (read_seqlock_retry(&clock_seqlock, seq));
		return nsec;
		}
	case CLOCK128_MULT_SHIFT:
		return (unsigned long long)((t * clock_mult128) >> clock_shift);
		default:
			assert(0);
	}
}

static unsigned long long get_nsec(int mode, unsigned long long t)
{
	if (mode == CLOCK64_LOCK) {
		update_clock(t);
	}

	return _get_nsec(mode, t);
}

static void calc_mult_shift(int mode, void *mult, unsigned int *shift,
			    unsigned long long max_sec,
			    unsigned long long cycles_per_usec)
{
	unsigned long long max_ticks;
	max_ticks = max_sec * cycles_per_usec * 1000000ULL;

	switch (mode) {
	case CLOCK64_MULT_SHIFT: {
		unsigned long long max_mult, tmp;
		unsigned int sft = 0;

		/*
		 * Calculate the largest multiplier that will not
		 * produce a 64-bit overflow in the multiplication
		 * step of the clock ticks to nsec conversion
		 */
		max_mult = ULLONG_MAX / max_ticks;
		dprintf("max_ticks=%llu, __builtin_clzll=%d, max_mult=%llu\n", max_ticks, __builtin_clzll(max_ticks), max_mult);

		/*
		 * Find the largest shift count that will produce
		 * a multiplier less than max_mult
		 */
		tmp = max_mult * cycles_per_usec / 1000;
		while (tmp > 1) {
			tmp >>= 1;
			sft++;
			dprintf("tmp=%llu, sft=%u\n", tmp, sft);
		}

		*shift = sft;
		*((unsigned long long *)mult) = (unsigned long long) ((1ULL << sft) * 1000 / cycles_per_usec);
		break;
		}
	case CLOCK64_EMULATE_128: {
		unsigned long long max_mult[2], tmp[2] = { };
		unsigned int sft = 0;

		/*
		 * Calculate the largest multiplier that will not
		 * produce a 128-bit overflow in the multiplication
		 * step of the clock ticks to nsec conversion,
		 * but use only 64-bit integers in the process
		 */
		max_mult[0] = max_mult[1] = ULLONG_MAX;
		do_div(max_mult, max_ticks, max_mult);
		dprintf("max_ticks=%llu, __builtin_clzll=%d, max_mult=0x%016llx%016llx\n",
			max_ticks, __builtin_clzll(max_ticks), max_mult[1], max_mult[0]);

		/*
		 * Find the largest shift count that will produce
		 * a multiplier less than max_mult
		 */
		do_div(max_mult, cycles_per_usec, tmp);
		do_div(tmp, 1000ULL, tmp);
		while (tmp[0] > 1 || tmp[1] > 1) {
			do_shift(tmp, 1);
			sft++;
			dprintf("tmp=0x%016llx%016llx, sft=%u\n", tmp[1], tmp[0], sft);
		}

		*shift = sft;
//		*((unsigned long long *)mult) = (__uint128_t) (((__uint128_t)1 << sft) * 1000 / cycles_per_usec);
		break;
		}
	case CLOCK64_2STAGE: {
		unsigned long long tmp;
/*
 * This clock tick to nsec conversion requires two stages.
 *
 * Stage 1: Determine how many ~MAX_CLOCK_SEC_2STAGE periods worth of clock ticks
 * 	have elapsed and set nsecs to the appropriate value for those
 *	~MAX_CLOCK_SEC_2STAGE periods.
 * Stage 2: Subtract the ticks for the elapsed ~MAX_CLOCK_SEC_2STAGE periods from
 *	Stage 1. Convert remaining clock ticks to nsecs and add to previously
 *	set nsec value.
 *
 * To optimize the arithmetic operations, use the greatest power of 2 ticks
 * less than the number of ticks in MAX_CLOCK_SEC_2STAGE seconds.
 *
 */
		// Use a period shorter than MAX_CLOCK_SEC here for better accuracy
		calc_mult_shift(CLOCK64_MULT_SHIFT, mult, shift, MAX_CLOCK_SEC_2STAGE, cycles_per_usec);

		// Find the greatest power of 2 clock ticks that is less than the ticks in MAX_CLOCK_SEC_2STAGE
		max_cycles_shift = max_cycles_mask = 0;
		tmp = MAX_CLOCK_SEC_2STAGE * 1000000ULL * cycles_per_usec;
		dprintf("tmp=%llu, max_cycles_shift=%u\n", tmp, max_cycles_shift);
		while (tmp > 1) {
			tmp >>= 1;
			max_cycles_shift++;
			dprintf("tmp=%llu, max_cycles_shift=%u\n", tmp, max_cycles_shift);
		}
		// if use use (1ULL << max_cycles_shift) * 1000 / cycles_per_usec here we will
		// have a discontinuity every (1ULL << max_cycles_shift) cycles
		nsecs_for_max_cycles = (1ULL << max_cycles_shift) * *((unsigned long long *)mult) >> *shift;

		// Use a bitmask to calculate ticks % (1ULL << max_cycles_shift)
		for (tmp = 0; tmp < max_cycles_shift; tmp++)
			max_cycles_mask |= 1ULL << tmp;

		dprintf("max_cycles_shift=%u, 2^max_cycles_shift=%llu, nsecs_for_max_cycles=%llu, max_cycles_mask=%016llx\n",
				max_cycles_shift, (1ULL << max_cycles_shift),
				nsecs_for_max_cycles, max_cycles_mask);


		break;
		}
	case CLOCK64_LOCK: {
/*
 * This clock tick to nsec conversion also requires two stages.
 *
 * Stage 1: Add to nsec the current running total of elapsed long periods
 * Stage 2: Subtract from clock ticks the tick count corresponding to the
 *	most recently elapsed long period. Convert the remaining ticks to
 *	nsec and add to the previous nsec value.
 *
 * In practice the elapsed nsec from Stage 1 and the tick count subtracted
 * in Stage 2 will be maintained in a separate thread.
 *
 */
		calc_mult_shift(CLOCK64_2STAGE, mult, shift, MAX_CLOCK_SEC, cycles_per_usec);
		cycles_start = 0;
		break;
		}
	case CLOCK128_MULT_SHIFT: {
		__uint128_t max_mult, tmp;
		unsigned int sft = 0;

		/*
		 * Calculate the largest multiplier that will not
		 * produce a 128-bit overflow in the multiplication
		 * step of the clock ticks to nsec conversion
		 */
		max_mult = ((__uint128_t) ULLONG_MAX) << 64 | ULLONG_MAX;
		max_mult /= max_ticks;
		dprintf("max_ticks=%llu, __builtin_clzll=%d, max_mult=0x%016llx%016llx\n",
				max_ticks, __builtin_clzll(max_ticks),
				(unsigned long long) (max_mult >> 64),
				(unsigned long long) max_mult);

		/*
		 * Find the largest shift count that will produce
		 * a multiplier less than max_mult
		 */
		tmp = max_mult * cycles_per_usec / 1000;
		while (tmp > 1) {
			tmp >>= 1;
			sft++;
			dprintf("tmp=0x%016llx%016llx, sft=%u\n",
					(unsigned long long) (tmp >> 64),
					(unsigned long long) tmp, sft);
		}

		*shift = sft;
		*((__uint128_t *)mult) = (__uint128_t) (((__uint128_t)1 << sft) * 1000 / cycles_per_usec);
		break;
		}
	}
}

static int discontinuity(int mode, int delta_ticks, int delta_nsec,
			 unsigned long long start, unsigned long len)
{
	int i;
	unsigned long mismatches = 0, bad_mismatches = 0;
	unsigned long long delta, max_mismatch = 0;
	unsigned long long *ns = nsecs;

	for (i = 0; i < len; ns++, i++) {
		*ns = get_nsec(mode, start + i);
		if (i - delta_ticks >= 0) {
			if (*ns > *(ns - delta_ticks))
				delta = *ns - *(ns - delta_ticks);
			else
				delta = *(ns - delta_ticks) - *ns;
			if (delta > delta_nsec)
				delta -= delta_nsec;
			else
				delta = delta_nsec - delta;
			if (delta) {
				mismatches++;
				if (delta > 1)
					bad_mismatches++;
				if (delta > max_mismatch)
					max_mismatch = delta;
			}
		}
		if (!bad_mismatches)
			assert(max_mismatch == 0 || max_mismatch == 1);
		if (!mismatches)
			assert(max_mismatch == 0);
	}

	printf("%lu discontinuities (%lu%%) (%lu errors > 1ns, max delta = %lluns) for ticks = %llu...%llu\n",
		mismatches, (mismatches * 100) / len, bad_mismatches, max_mismatch, start,
		start + len - 1);
	return mismatches;
}

#define MIN_TICKS 1ULL
#define LEN 1000000000ULL
#define NSEC_ONE_SEC 1000000000ULL
#define TESTLEN 9

static long long test_clock(int mode, int cycles_per_usec, int fast_test,
			    int quiet, int delta_ticks, int delta_nsec)
{
	int i;
	long long delta;
	unsigned long long max_ticks;
	unsigned long long nsecs;
	void *mult;
	unsigned long long test_ns[TESTLEN] =
			{NSEC_ONE_SEC, NSEC_ONE_SEC,
			 NSEC_ONE_SEC, NSEC_ONE_SEC*60, NSEC_ONE_SEC*60*60,
			 NSEC_ONE_SEC*60*60*2, NSEC_ONE_SEC*60*60*4,
			 NSEC_ONE_SEC*60*60*8, NSEC_ONE_SEC*60*60*24};
	unsigned long long test_ticks[TESTLEN];

	max_ticks = MAX_CLOCK_SEC * (unsigned long long) cycles_per_usec * 1000000ULL;

	switch(mode) {
	case CLOCK64_MULT_SHIFT:
		mult = &clock_mult;
		break;
	case CLOCK64_EMULATE_128:
		mult = clock_mult64_128;
		break;
	case CLOCK64_2STAGE:
		mult = &clock_mult;
		break;
	case CLOCK64_LOCK:
		mult = &clock_mult;
		break;
	case CLOCK128_MULT_SHIFT:
		mult = &clock_mult128;
		break;
	default:
		assert(0);
	}
	calc_mult_shift(mode, mult, &clock_shift, MAX_CLOCK_SEC, cycles_per_usec);
	nsecs = get_nsec(mode, max_ticks);
	delta = nsecs/1000000 - MAX_CLOCK_SEC*1000;

	if (mode == CLOCK64_2STAGE) {
		test_ns[0] = nsecs_for_max_cycles - 1;
		test_ns[1] = nsecs_for_max_cycles;
		test_ticks[0] = (1ULL << max_cycles_shift) - 1;
		test_ticks[1] = (1ULL << max_cycles_shift);

		for (i = 2; i < TESTLEN; i++)
			test_ticks[i] = test_ns[i] / 1000 * cycles_per_usec;
	}
	else {
		for (i = 0; i < TESTLEN; i++)
			test_ticks[i] = test_ns[i] / 1000 * cycles_per_usec;
	}

	if (!quiet) {
		printf("cycles_per_usec=%d, delta_ticks=%d, delta_nsec=%d, max_ticks=%llu, shift=%u, 2^shift=%llu\n",
			cycles_per_usec, delta_ticks, delta_nsec, max_ticks, clock_shift, (1ULL << clock_shift));
		switch(mode) {
			case CLOCK64_LOCK:
			case CLOCK64_2STAGE:
			case CLOCK64_MULT_SHIFT: {
				printf("clock_mult=%llu, clock_mult / 2^clock_shift=%f\n",
					clock_mult, (double) clock_mult / (1ULL << clock_shift));
				break;
			}
			case CLOCK64_EMULATE_128: {
				printf("clock_mult=0x%016llx%016llx\n",
					clock_mult64_128[1], clock_mult64_128[0]);
				break;
			}
			case CLOCK128_MULT_SHIFT: {
				printf("clock_mult=0x%016llx%016llx\n",
					(unsigned long long) (clock_mult128 >> 64),
					(unsigned long long) clock_mult128);
				break;
			}
		}
		printf("get_nsec(max_ticks) = %lluns, should be %lluns, error<=abs(%lld)ms\n",
			nsecs, MAX_CLOCK_SEC*1000000000ULL, delta);
	}

	for (i = 0; i < TESTLEN; i++)
	{
		nsecs = get_nsec(mode, test_ticks[i]);
		delta = nsecs > test_ns[i] ? nsecs - test_ns[i] : test_ns[i] - nsecs;
		if (!quiet || delta > 0)
			printf("get_nsec(%llu)=%llu, expected %llu, delta=%llu\n",
				test_ticks[i], nsecs, test_ns[i], delta);
	}

	if (!fast_test) {
		discontinuity(mode, delta_ticks, delta_nsec, max_ticks - LEN + 1, LEN);
		discontinuity(mode, delta_ticks, delta_nsec, MIN_TICKS, LEN);
	}

	if (!quiet)
		printf("\n\n");

	return delta;
}

int main(int argc, char *argv[])
{
	nsecs = malloc(LEN * sizeof(unsigned long long));

	test_clock(CLOCK64_LOCK, 3333, 1, 0, 0, 0);
	test_clock(CLOCK64_LOCK, 1000, 1, 0, 1, 1);
	test_clock(CLOCK64_LOCK, 1100, 1, 0, 11, 10);
	test_clock(CLOCK64_LOCK, 3000, 1, 0, 3, 1);
	test_clock(CLOCK64_LOCK, 3333, 1, 0, 3333, 1000);
	test_clock(CLOCK64_LOCK, 3392, 1, 0, 424, 125);
	test_clock(CLOCK64_LOCK, 4500, 1, 0, 9, 2);
	test_clock(CLOCK64_LOCK, 5000, 1, 0, 5, 1);

	free(nsecs);
	return 0;
}