/*
 * TLB miss measurement on x86 CPUs.
 *
 * Copyright (C) 1999, Ingo Molnar <mingo@redhat.com>
 */
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/wait.h>
#include <sys/mman.h>

#define BYTES (512*1024*1024)
#define PAGES (BYTES/4096)

/* This define turns on the linear mode.. */
#define NONRANDOM 0

#if 1
# define BARRIER "cli; mfence; \n"
#else
# define BARRIER "lock ; addl $0,0(%%esp)\n"
#endif

#define rdtscll(val) \
     __asm__ __volatile__ ("rdtsc;" : "=A" (val))

int do_test (char * addr)
{
	unsigned long start = -1, end = -1;
	/*
	 * 'cli' is used as a serializing instruction to
	 * isolate the benchmarked instruction from rdtsc.
	 */
	__asm__ (
BARRIER
"		rdtsc; \n"
"		movl %%eax, %1\n"
BARRIER
"		# start of benchmarked section;\n"
"		movl (%%esi), %%eax; \n"
"		# end of benchmarked section; \n"
BARRIER
"		rdtsc; \n"
BARRIER

		:"=a" (end), "=c" (start)
		:"S" (addr)
		:"dx","memory");
	return end - start;
}

extern int iopl(int);

void main (void)
{
	unsigned long overhead;
	int j, k, c, hit;
	int matrix [PAGES];
	int delta [PAGES];
	char *buffer = mmap(NULL, BYTES, PROT_READ|PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

	memset(buffer, 0, BYTES);
	mprotect(buffer, BYTES, PROT_READ);
	iopl(3);
	/*
	 * first generate a random access pattern.
	 */
	for (j = 0; j < PAGES; j++) {
		unsigned long val;
#if NONRANDOM
		val = ((j*8) % PAGES) * 4096;
		val = j*2048;
#else
		unsigned long long t;
		unsigned int a0, a1;
		// randomize harder
		rdtscll(t);
		a0 = ((int *)&t)[0];
		a1 = ((int *)&t)[1];
		val = ((random() + a0 + a1) % PAGES) * 4096;
#endif
		matrix[j] = val;
	}

	/*
	 * Calculate the overhead
	 */
	overhead = ~0UL;
	for (j = 0; j < 100; j++) {
		unsigned int diff = do_test(buffer);
		if (diff < overhead)
			overhead = diff;
	}
	printf("Overhead = %ld cycles\n", overhead);

	/*
	 * 10 warmup loops, the last one is printed.
	 */
	for (k = 0; k < 10; k++) {
		c = 0;
		for (j = 0; j < PAGES; j++) {
			char * addr;
			addr = buffer + matrix[j];
			delta[c++] = do_test(addr);
		}
	}
	hit = 0;
//	for (j = 0; j < PAGES; j++) {
	for (j = PAGES-1; j >= 0; j--) {
		unsigned long d = delta[j] - overhead;
		printf("%ld ", d);
		if (d <= 1)
			hit++;
	}
	printf("\n");
	printf("%d %s accessed pages, %f%% TLB misses.\n", PAGES,
#if NONRANDOM
	"linearly",
#else
	"randomly",
#endif
			100.0*((double)PAGES-(double)hit)/(double)PAGES);
}