To:	linux-kernel@vger.rutgers.edu
Subject: Announce: libvtimer
Date:	Fri, 18 Jun 1999 13:03:37 EDT
From:	Dan Adkins <dadkins@MIT.EDU>

I just implemented libvtimer, a high resolution virtual timer library
for Linux based upon the Pentium cycle counter (aka TSC).  You can
download it (for now) from the Internet at:
	 http://web.mit.edu/~dadkins/Public/vtimer-0.1.tar.gz
It contains a patch to kernel version 2.3.6 and a user library to use it.

The basic goal of this patch and library was to add per-process timers to
Linux with a much higher resolution than times(), and with a much lower
ovehead to access them (cause a precise timer does you no good if you takes
you milliseconds to access).  Inside the kernel, the task structure is
updated with an additional structure for book-keeping purposes.  Each time
the scheduler is invoked to switch processes, two times are updated for
a process.
	1: The time the process is being switched in. (start_time)
	2: The total running time of the process (if it's being switched out)
		calculated by (elapsed_time += current_time - start_time)

The instruction RDTSC can be executed in user mode to determine the value of
the cycle counter.  In order to allow the user to calculate it's own virtual
elapsed time up to the moment, it needs to read the value, and the two values
the kernel maintains.  Then: 
	virtual_time = elapsed_time + (current_time - start_time)
To keep the overhead of this operation low, the timer structure is actually
kept in user memory, and the kernel just has a pointer to it.  Yes, this
makes things a little tricky, but the kernel just needs to validate the
memory location when the timer is installed and the user passes a pointer to
it. 

One more complication arises when keeping this operation in user space.  It's
possible for a process to get switched out in the middle of the computation
making some parts of it inconsistent.  To avoid this problem, we implement
a nonblocking version of this calculation in vtimer_get_elapsed() (in the
user library) that in essence checks to make sure that values it reads haven't
changed after it reads them all in.  Then everything is fine and the error
is minimal.

In practice, the cost of calling vtimer_get_elapsed() to determine a process's
virtual elapsed time is just 80 cycles, as opposed to a call to gettimeofday()
which takes about 500 cycles.  This, in our opinion is a low enough error
for the purposes of this timer and doesn't affect the times we're trying to
measure to much.  I thought of trying to account for the time it takes
to get this time, but it's not worth the effort and doesn't really give
anthing meaningful in return.

Any comments, suggestions, whatever?  You can find out more by downloading
the patch for 2.3.6 and the library at
	http://web.mit.edu/~dadkins/Public/vtimer-0.1.tar.gz

-Dan Adkins

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