A better interface, perhaps: a timed signal flag

A better interface, perhaps: a timed signal flag

[Theodore Tso]

On Tue, Jul 25, 2006 at 08:20:43PM -0400, Neil Horman wrote:
> > Yes, there are plenty of systems which don't have an RTC, or have an RTC 
> > which can't generate interrupts.
> > 
> Ok, for those implementations which don't have an RTC that the rtc driver can
> drive, the mmap functionality will not work, but at that point what interface
> are you left with at all for obtaining periodic time?

Well, the HPET, for one.  My main problem with this interface is that
it is tied to the /dev/rtc, and the system may have any number of
timer hardware that may be more appropriate, and it shouldn't be up to
the user application to select which one.

But this does bring up an interesting coding paradigm which is used by
more than just the X server.  As it turns out, there is a real-time
garbage collector[1] for Java that needs exactly the same thing, although
the resolution window is a few orders of magnitude faster than what X
needs.  Fundamentally, this coding paradigm is:

	while (work to do) {
		do_a_bit_of_work();
		if (we_have_exceeded_a_timeout_period())
			break;  
	}
	/* Clean up and let some other client/thread run */

So there are a couple of things to note about this high-level
abstracted paradigm.  The application doesn't need to know _exactly_
how much time has passed, just whether or not the the appointed time
slice has expired (which might be 10ms or it might be 100us in the
case of the rt garbage collector).  So calculating exactly how much
time has ellapsed is not necessary, and if there is a single-shot
event timer hardware available to the system, it might be sufficient.
So even if a VDSO implementation of gettimeofday() would be faster
than calling gettimeofday(), it still may be doing work that strictly
speaking doesn't need to happen; if the application doesn't need to
know exactly how many microseconds have gone by, but just whether or
not 150us has ellapsed, why calculate the necessary time?  (Especially
if it requires using some ACPI interface...)

Secondly, it's different from a kernel-mediated secheduler timeslice
because the application needs to give up control only at certain
specifically defined stopping points (i.e., after copying a tiny
amount of live data in an incremental garbage collector design, or
after servicing a single X request, for example), and it may need to
do some cleanups.  So it's often not possible to just say, well, put
it in its own thread, and let the scheduler handle it. 

So maybe what we need is an interface where a particular memory
location gets incremented when a timeout has happened.  It's probably
enough to say that each thread (task_struct) can have one of these
(another problem with using /dev/rtc and tieing it directly to
interrupts is that what happens if two processes want to use this
facility?), and what hardware timer source gets used is hidden from
the user application.  In fact, depending on the resolution which is
specified (i.e., 100's of microseconds versus 10's of milliseconds),
different hardware might get used; we should leave that up to the
kernel.

The other thing which would be nice is if the application could
specify whether it is interested in CPU time or wall clock time for
this timeout.

If we had such an interface, then the application would look like
this:

	volatile int	flag = 0;

	register_timout(&time_val, &flag);
	while (work to do) {
		do_a_bit_of_work();
		if (flag)
			break;
	}

Finally, a note about tickless designs.  Very often such applications
don't need a constantly ticking design.  For example, the X server
only needs to have the memory location incremented while it is
processing events; if the laptop is idle, there's no reason to have
the RTC generating interrupts and incrementing memory locations.
Similarly, the Metronome garbage collector would only need to poll to
see if the timeout has expired while the garbage collector is running,
which is _not_ all of the time.  

Yes, you could use ioctl's to start and stop the RTC interrupt
handler, but that's just ugly, and points out that maybe the interface
should not be one of programming the RTC interrupt frequency directly,
but rather one of "increment this flag after X units of
(CPU/wallclock) time, and I don't care how it is implemented at the
hardware level."

Regards,

						- Ted

[1] http://www.research.ibm.com/people/d/dfb/papers/Bacon03Metronome.pdf
"The Metronome: A Simpler Approach to Garbage Collection in Real-time
Systems", by David Bacon, Perry Cheng, and V.T. Rajan, Workshop on
Java Technologies for Real-Time and Embedded Systems (Catania, Sicily,
November 2003.  (See also http://www.research.ibm.com/metronome)

RE: A better interface, perhaps: a timed signal flag

[Brown, Len]

>if the application doesn't need to
>know exactly how many microseconds have gone by, but just whether or
>not 150us has ellapsed, why calculate the necessary time?  (Especially
>if it requires using some ACPI interface...)

Yes, ACPI is involved in the boot-time enumeration of various timers
and counters.  But at run-time; the use of any and all of them
(including the PM_TIMER supplied by ACPI hardware itself) could/should
appear generic to kernel users, who should not have to directly call
any routine with an "acpi" in it.

I believe that this is true today, and can/should stay true.

-Len

Re: A better interface, perhaps: a timed signal flag

[Steven Rostedt]

On Wed, 2006-07-26 at 10:45 -0400, Theodore Tso wrote:

> If we had such an interface, then the application would look like
> this:
> 
> 	volatile int	flag = 0;
> 
> 	register_timout(&time_val, &flag);
> 	while (work to do) {
> 		do_a_bit_of_work();
> 		if (flag)
> 			break;
> 	}

This wouldn't work simply because the timeout would most likely be
implemented with an interrupt, and the address of flag is in userspace,
so the interrupt handler couldn't modify it (without doing some sort of
single handling, and thus slow down what you want).

What you could have is this:

  volatile int *flag;

  register_timeout(&time_val, &flag);
  while (work_to_do()) {
	do_a_bit_of_work();
	if (*flag)
		break;
  }

Where the kernel would register a location to set a timeout with, and
the kernel would setup a flag for you and then map it into userspace.
Perhaps only allow one flag per task and place it as a field of the task
structure.  There's no reason that the tasks own task sturct cant be
mapped read only to user space, is there?

-- Steve

Re: A better interface, perhaps: a timed signal flag

[Theodore Tso]

On Fri, Jul 28, 2006 at 09:33:26AM -0400, Steven Rostedt wrote:
> What you could have is this:
> 
>   volatile int *flag;
> 
>   register_timeout(&time_val, &flag);
>   while (work_to_do()) {
> 	do_a_bit_of_work();
> 	if (*flag)
> 		break;
>   }
> 
> Where the kernel would register a location to set a timeout with, and
> the kernel would setup a flag for you and then map it into userspace.
> Perhaps only allow one flag per task and place it as a field of the task
> structure.  There's no reason that the tasks own task sturct cant be
> mapped read only to user space, is there?

Good point, and limiting this facility to one such timeout per
task_struct seems like a reasonable restriction.  The downsides I can
see about about mapping the tasks' own task struct would be (a) a
potential security leak either now or in the future if some field in
the task_struct shouldn't be visible to a non-privileged userspace
program, and (b) exposing the task_struct might cause some (stupid)
programs to depend on the task_struct layout.  Allocating an otherwise
empty 4k page just for this purpose wouldn't be all that horrible,
though, and would avoid these potential problems.

							- Ted

Re: A better interface, perhaps: a timed signal flag

[Steven Rostedt]

On Fri, 2006-07-28 at 10:52 -0400, Theodore Tso wrote:

> Good point, and limiting this facility to one such timeout per
> task_struct seems like a reasonable restriction.  The downsides I can
> see about about mapping the tasks' own task struct would be (a) a
> potential security leak either now or in the future if some field in
> the task_struct shouldn't be visible to a non-privileged userspace
> program, and (b) exposing the task_struct might cause some (stupid)
> programs to depend on the task_struct layout.  Allocating an otherwise
> empty 4k page just for this purpose wouldn't be all that horrible,
> though, and would avoid these potential problems.

Actually, if you are going to map a page, then allow the user to do
PAGE_SIZE / sizeof(*flag) timers.  That way the user gets a single page
mapped for this purpose, and can have multiple flags.

I would only limit it to one page though. Since this page can not be
swapped out, if you allow for more than one page, a non privileged user
can map in a bunch of non swappable pages and might be able to perform a
DoS attack.

-- Steve

Re: A better interface, perhaps: a timed signal flag

[Alan Cox]

Ar Gwe, 2006-07-28 am 10:52 -0400, ysgrifennodd Theodore Tso:
> Good point, and limiting this facility to one such timeout per
> task_struct seems like a reasonable restriction. 

Why is this any better than using a thread or signal handler ? From the
implementation side its certainly horrible - we will be trying to write
user pages from an IRQ event. Far better to let the existing thread code
deal with it.

Re: A better interface, perhaps: a timed signal flag

[Steven Rostedt]

On Fri, 2006-07-28 at 17:41 +0100, Alan Cox wrote:
> Ar Gwe, 2006-07-28 am 10:52 -0400, ysgrifennodd Theodore Tso:
> > Good point, and limiting this facility to one such timeout per
> > task_struct seems like a reasonable restriction. 
> 
> Why is this any better than using a thread or signal handler ? From the
> implementation side its certainly horrible - we will be trying to write
> user pages from an IRQ event. Far better to let the existing thread code
> deal with it.
> 

If the user page is special, in that it is really a kernel page mapped
to userspace.  The implementation on making sure it doesn't disappear on
the interrupt isn't that difficult.

But for real-time applications, the signal handling has a huge latency.
Where as what Theodore wants to do is very light weight.  ie. have a
high prio task doing smaller tasks until a specific time that tells it
to stop.  Having a signal, would create the latency on having that task
stop.

These little requests make sense really only in the real-time space.
The normal uses can get by with signals.  But I will say, the normal
uses for computing these days are starting to want the real-time
powers. :)

-- Steve

Re: A better interface, perhaps: a timed signal flag

[H. Peter Anvin]

> 
> So maybe what we need is an interface where a particular memory
> location gets incremented when a timeout has happened.  It's probably
> enough to say that each thread (task_struct) can have one of these
> (another problem with using /dev/rtc and tieing it directly to
> interrupts is that what happens if two processes want to use this
> facility?), and what hardware timer source gets used is hidden from
> the user application.  In fact, depending on the resolution which is
> specified (i.e., 100's of microseconds versus 10's of milliseconds),
> different hardware might get used; we should leave that up to the
> kernel.
> 
> The other thing which would be nice is if the application could
> specify whether it is interested in CPU time or wall clock time for
> this timeout.
> 

It seems to me that this still assumes that we need to take an interrupt 
in the kernel.  If so, why not just use the timers already present in 
the kernel as opposed to polling gettimeofday()?

	-hpa

Re: A better interface, perhaps: a timed signal flag

[Alan Cox]

Ar Gwe, 2006-07-28 am 12:44 -0400, ysgrifennodd Steven Rostedt:
> But for real-time applications, the signal handling has a huge latency.

For real-time you want a thread. Our thread switching is extremely fast
and threads unlike signals can have RT priorities of their own

Re: A better interface, perhaps: a timed signal flag

[Steven Rostedt]

On Fri, 2006-07-28 at 21:01 +0100, Alan Cox wrote:
> Ar Gwe, 2006-07-28 am 12:44 -0400, ysgrifennodd Steven Rostedt:
> > But for real-time applications, the signal handling has a huge latency.
> 
> For real-time you want a thread. Our thread switching is extremely fast
> and threads unlike signals can have RT priorities of their own
> 

You mean to have a thread that does a nanosleep till the expected
timeout, then write some variable that the other high prio thread can
see that the timeout has expired?

Hmm, so that register_timeout can be implemented with at thread that
does a nanosleep then updates the flag.

The only problem is that the thread needs to go up to a higher priority
(perhaps the highest), which means that this can only be implemented
with special capabilities. Then again, pretty much all RT tasks are
special, and usually run with privileged capabilities.


There's also something else that would be a nice addition to the kernel
API.  A sleep and wakeup that is implemented without signals. Similar to
what the kernel does with wake_up.  That way you can sleep till another
process/thread is done with what it was doing and wake up the other task
when done, without the use of signals.  Or is there something that
already does this?

-- Steve

Re: A better interface, perhaps: a timed signal flag

[Steven Rostedt]

On Fri, 2006-07-28 at 21:36 +0100, Alan Cox wrote:
> Ar Gwe, 2006-07-28 am 16:12 -0400, ysgrifennodd Steven Rostedt:

So what language does the above come from ;-) "Ar Gwe" "ysgrifennodd" ?

> > what the kernel does with wake_up.  That way you can sleep till another
> > process/thread is done with what it was doing and wake up the other task
> > when done, without the use of signals.  Or is there something that
> > already does this?
> 
> futex and sys5 semaphore both do this. The latter is very portable but a
> bit less efficient.

semaphore is a bit awkward for this (I have implemented it for this type
of purpose and it really feels like a hack).

How can this be implemented with futex??  Let me make another scenario.
If you have a task sleeping and it needs to be woken when some other
task needs it (kind of like a kthread) but it doesn't know what task
will wake it.  A futex is like a mutex where it has one owner, so you
can sleep till the owner awakes it, but you don't know who the owner is.

I really like the way the kernel has the wake_up_process function, and
it is vary handy to have for even user space.  Right now the most common
way to do it is semaphores (yuck!) or signals.  Both are very heavy and
I don't really see why a new interface can't be introduced.  Yes, it
breaks portability, but it if becomes a standard, then others  will port
to it (and maybe it will become a new POSIX standard :)

-- Steve

Re: A better interface, perhaps: a timed signal flag

[Alan Cox]

Ar Gwe, 2006-07-28 am 16:12 -0400, ysgrifennodd Steven Rostedt:
> what the kernel does with wake_up.  That way you can sleep till another
> process/thread is done with what it was doing and wake up the other task
> when done, without the use of signals.  Or is there something that
> already does this?

futex and sys5 semaphore both do this. The latter is very portable but a
bit less efficient.

Re: A better interface, perhaps: a timed signal flag

[linux]

> If we had such an interface, then the application would look like
> this:
> 
>	volatile int	flag = 0;
>
>	register_timout(&time_val, &flag);
>	while (work to do) {
>		do_a_bit_of_work();
>		if (flag)
>			break;
>	}
>
> Finally, a note about tickless designs.  Very often such applications
> don't need a constantly ticking design.  For example, the X server
> only needs to have the memory location incremented while it is
> processing events; if the laptop is idle, there's no reason to have
> the RTC generating interrupts and incrementing memory locations.
> Similarly, the Metronome garbage collector would only need to poll to
> see if the timeout has expired while the garbage collector is running,
> which is _not_ all of the time.  
> 
> Yes, you could use ioctl's to start and stop the RTC interrupt
> handler, but that's just ugly, and points out that maybe the interface
> should not be one of programming the RTC interrupt frequency directly,
> but rather one of "increment this flag after X units of
> (CPU/wallclock) time, and I don't care how it is implemented at the
> hardware level."

Actually, unless you want the kernel to have to poll the timeout_flag
periodically, it's more like:

	volatile bool	timeout_flag = false, armed_flag = false;

	register_timout(&time_val, &flag);
	while (work to do) {
		if (!armed_flag) {
			rearm_timeout();
			armed_flag = true;
		}
		do_a_bit_of_work();
		if (timeout_flag) {
			armed_flag = false;
			timeout_flag = false;
			break;
		}
	}

Personally, I use setitimer() for this.  You can maintain the flags in
software, and be slightly lazy about disarming it.  If you get a signal
while you shouldn't be armed, *then* disarm the timer in the kernel.
Likewise, when rearming, set the user-disarmed flag and chec if kernel-level
rearming is required.

volatile bool timeout_flag = false, armed_flag = false, sys_armed_flag = false;

void
sigalrm(int sig)
{
	(void)sig;
	if (!armed_flag) {
		static const struct itimerval it_zero = {{0,0},{0,0}};
		if (sys_armed_flag)
			warn_unexpected_sigalrm();
		setitimer(ITIMER_REAL, &it_zero, 0);
		
	} else if (timeout_flag)
		warn_gc_is_slow();
	else
		timeout_flag = true;
}

void
arm_timer()
{
	static const struct itimerval it_interval = { time_val, time_val };

	armed_flag = true;
	if (!sys_armed_flag) {
		setitimer(ITIMER_REAL, &it_interval, 0);
		sys_armed_flag = true;
	}
}

main_loop()
{
	signal(SIGALRM, sigalrm);

	while (work to do) {
		arm_timer();
		do_a_bit_of_work();
		if (timeout_flag) {
			gc();
			armed_flag = false;
			timeout_flag = false;
		}
	}
}

... where only do_a_bit_of_work can prompt the need for more gc() calls.
This really tries to minimize the number of system calls.

Re: A better interface, perhaps: a timed signal flag

[Robert Hancock]

Steven Rostedt wrote:
> There's also something else that would be a nice addition to the kernel
> API.  A sleep and wakeup that is implemented without signals. Similar to
> what the kernel does with wake_up.  That way you can sleep till another
> process/thread is done with what it was doing and wake up the other task
> when done, without the use of signals.  Or is there something that
> already does this?

For between threads, this is what the POSIX pthread API is for 
(pthread_cond_wait and friends) which is implemented using futexes these 
days..

-- 
Robert Hancock      Saskatoon, SK, Canada
To email, remove "nospam" from hancockr@nospamshaw.ca
Home Page: http://www.roberthancock.com/