futex and timeouts

futex and timeouts

[Hubertus Franke]

Ulrich, it seems to me that absolute timeouts are the easiest to do.

(a) expand by additional parameter (0) means no timeout desired
(b) differentiate the schedule call in futex_down..

Question is whether the granularity of jiffies (10ms) is sufficiently small 
for timeouts.....

Rusty, take a look, wether there's something wrong with this and see whether
you can integrate it or improve and integrate it.

/* Simplified from arch/ppc/kernel/semaphore.c: Paul M. is a genius. */
static int futex_down(struct list_head *head, struct page *page, int offset,  
                             signed long timeout)
{
        int retval = 0;
        struct futex_q q;
 
        current->state = TASK_INTERRUPTIBLE;
        queue_me(head, &q, page, offset);
 
        while (!decrement_to_zero(page, offset)) {
                if (signal_pending(current)) {
                        retval = -EINTR;
                        break;
                }
	    if (!timeout) {
	        schedule();
                    current->state = TASK_INTERRUPTIBLE;	
	        continue;
                }
	    delay = schedule_timeout(timeout);
	    if (delay == 0)  {
		retval = -EAGAIN;
		break;
	    }
	    current->state = TASK_INTERRUPTIBLE;
	    timeout -= delay;
        }
        current->state = TASK_RUNNING;
        unqueue_me(&q);
        /* If we were signalled, we might have just been woken: we
           must wake another one.  Otherwise we need to wake someone
           else (if they are waiting) so they drop the count below 0,
           and when we "up" in userspace, we know there is a
           waiter. */
        wake_one_waiter(head, page, offset);
        return retval;
}

-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)

Re: futex and timeouts

[Ulrich Drepper]

[-- Attachment #1: Type: text/plain, Size: 750 bytes --]

On Wed, 2002-03-13 at 10:26, Hubertus Franke wrote:

> Ulrich, it seems to me that absolute timeouts are the easiest to do.

Does it work with settimeofday()?


> Question is whether the granularity of jiffies (10ms) is sufficiently small 
> for timeouts.....

Hopefully there will be support for high-resolution clocks and timers
sometime soon.  I don't know how to prepare new interfaces for this.  I
guess there will be a whole bunch of interface changes/additions so you 
could ignore the problem for now.

-- 
---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 232 bytes --]

Re: futex and timeouts

[Rusty Russell]

In message <20020313182552.945523FE06@smtp.linux.ibm.com> you write:
> 
> Ulrich, it seems to me that absolute timeouts are the easiest to do.
> 
> (a) expand by additional parameter (0) means no timeout desired
> (b) differentiate the schedule call in futex_down..
> 
> Question is whether the granularity of jiffies (10ms) is sufficiently small 
> for timeouts.....

1) You must not export jiffies to userspace.

2) They are not a time, they are a counter, and they do wrap.

3) This does not handle the settimeofday case: you need to check in
   userspace for that anyway.

So, since you need to check if you're trying to sleep for longer than
(say) 49 days, AND you need to check if you are after the given
abstime in userspace anyway (settimeofday backwards), you might as
well convert to relative in userspace.

Sorry,
Rusty.
--
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

Re: futex and timeouts

[Hubertus Franke]

On Wednesday 13 March 2002 11:15 pm, Rusty Russell wrote:
> In message <20020313182552.945523FE06@smtp.linux.ibm.com> you write:
> > Ulrich, it seems to me that absolute timeouts are the easiest to do.
> >
> > (a) expand by additional parameter (0) means no timeout desired
> > (b) differentiate the schedule call in futex_down..
> >
> > Question is whether the granularity of jiffies (10ms) is sufficiently
> > small for timeouts.....
>
> 1) You must not export jiffies to userspace.
>
> 2) They are not a time, they are a counter, and they do wrap.
>
> 3) This does not handle the settimeofday case: you need to check in
>    userspace for that anyway.
>
> So, since you need to check if you're trying to sleep for longer than
> (say) 49 days, AND you need to check if you are after the given
> abstime in userspace anyway (settimeofday backwards), you might as
> well convert to relative in userspace.
>
> Sorry,
> Rusty.

3) I think one of us is misunderstanding (its probably me)

What I was proposing was a relative wall clock time, vs application virtual 
time. 

interface would be to always specify in futex how long to wait (relative) and 
not until when to wait (absolute).
What I propose is not to export jiffies (ofcourse not), but either usecs or 
msecs and whether one should state what the minimum wait time is.
Right now we know it can't be less then 10ms (x86) unless we busywait and
above that the granularity will be in 10ms increments.

So from the previous post of code example, one has to add the conversion from
timeout to timeout_jiffies.
Also we need to determine the best API for this. Somebody (Rusty ?) suggest to
pass a pointer to (struct timeval) vs a single counter. Only disadvantage is 
an additional copy_from_user, but it gives much bigger timeouts.

I think its a good idea to add it.
-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)

[PATCH] Re: futex and timeouts

[Rusty Russell]

In message <20020314151846.EDCBF3FE07@smtp.linux.ibm.com> you write:
> 3) I think one of us is misunderstanding (its probably me)
> 
> What I was proposing was a relative wall clock time, vs application virtual 
> time. 
> 
> interface would be to always specify in futex how long to wait (relative) and
> not until when to wait (absolute).

Yep, sorry, my mistake.  I suggest make it a relative "struct timespec
*" (more futureproof that timeval).  It would make sense to split the
interface into futex_down and futex_up syuscalls, since futex_up
doesn't need a timeout arg, but I haven't for the moment.

(Untested) patch below,
Rusty.
--
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.7-pre1/kernel/futex.c working-2.5.7-pre1-futex-timeout/kernel/futex.c
--- linux-2.5.7-pre1/kernel/futex.c	Wed Mar 13 13:30:39 2002
+++ working-2.5.7-pre1-futex-timeout/kernel/futex.c	Fri Mar 15 16:37:14 2002
@@ -32,6 +32,7 @@
 #include <linux/fs.h>
 #include <linux/futex.h>
 #include <linux/highmem.h>
+#include <linux/time.h>
 #include <asm/atomic.h>
 
 /* These mutexes are a very simple counter: the winner is the one who
@@ -146,10 +147,19 @@
 }
 
 /* Simplified from arch/ppc/kernel/semaphore.c: Paul M. is a genius. */
-static int futex_down(struct list_head *head, struct page *page, int offset)
+static int futex_down(struct list_head *head, struct page *page, int offset,
+		      struct timespec *utime)
 {
 	int retval = 0;
 	struct futex_q q;
+	unsigned long time = MAX_SCHEDULE_TIMEOUT;
+
+	if (utime) {
+		struct timespec t;
+		if (copy_from_user(&t, utime, sizeof(t)) != 0)
+			return -EFAULT;
+		time = timespec_to_jiffies(&t) + 1;
+	}
 
 	current->state = TASK_INTERRUPTIBLE;
 	queue_me(head, &q, page, offset);
@@ -159,13 +169,17 @@
 			retval = -EINTR;
 			break;
 		}
-		schedule();
+		time = schedule_timeout(time);
+		if (time == 0) {
+			retval = -ETIMEDOUT;
+			break;
+		}
 		current->state = TASK_INTERRUPTIBLE;
 	}
 	current->state = TASK_RUNNING;
 	unqueue_me(&q);
-	/* If we were signalled, we might have just been woken: we
-	   must wake another one.  Otherwise we need to wake someone
+	/* If we were signalled, or timed out, we might have just been woken:
+	   we must wake another one.  Otherwise we need to wake someone
 	   else (if they are waiting) so they drop the count below 0,
 	   and when we "up" in userspace, we know there is a
 	   waiter. */
@@ -185,7 +199,7 @@
 	return 0;
 }
 
-asmlinkage int sys_futex(void *uaddr, int op)
+asmlinkage int sys_futex_down(void *uaddr, int op, struct timespec *utime)
 {
 	int ret;
 	unsigned long pos_in_page;
@@ -210,7 +224,7 @@
 		ret = futex_up(head, page, pos_in_page);
 		break;
 	case FUTEX_DOWN:
-		ret = futex_down(head, page, pos_in_page);
+		ret = futex_down(head, page, pos_in_page, utime);
 		break;
 	/* Add other lock types here... */
 	default:

Re: [PATCH] Re: futex and timeouts

[Joel Becker]

On Fri, Mar 15, 2002 at 04:39:50PM +1100, Rusty Russell wrote:
> Yep, sorry, my mistake.  I suggest make it a relative "struct timespec
> *" (more futureproof that timeval).  It would make sense to split the
> interface into futex_down and futex_up syuscalls, since futex_up
> doesn't need a timeout arg, but I haven't for the moment.

	Why waste a syscall?  The user is going to be using a library
wrapper.  They don't have to know that futex_up() calls sys_futex(futex,
FUTEX_UP, NULL);

Joel

-- 

Life's Little Instruction Book #182

	"Be romantic."

			http://www.jlbec.org/
			jlbec@evilplan.org

Re: [PATCH] Re: futex and timeouts

[H. Peter Anvin]

Followup to:  <20020315060829.L4836@parcelfarce.linux.theplanet.co.uk>
By author:    Joel Becker <jlbec@evilplan.org>
In newsgroup: linux.dev.kernel
>
> On Fri, Mar 15, 2002 at 04:39:50PM +1100, Rusty Russell wrote:
> > Yep, sorry, my mistake.  I suggest make it a relative "struct timespec
> > *" (more futureproof that timeval).  It would make sense to split the
> > interface into futex_down and futex_up syuscalls, since futex_up
> > doesn't need a timeout arg, but I haven't for the moment.
> 
> 	Why waste a syscall?  The user is going to be using a library
> wrapper.  They don't have to know that futex_up() calls sys_futex(futex,
> FUTEX_UP, NULL);
> 

Syscalls are (by and large) cheap.  Extra dispatches, however, hurt.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt	<amsp@zytor.com>

Re: [PATCH] Re: futex and timeouts

[Rusty Russell]

In message <20020315060829.L4836@parcelfarce.linux.theplanet.co.uk> you write:
> On Fri, Mar 15, 2002 at 04:39:50PM +1100, Rusty Russell wrote:
> > Yep, sorry, my mistake.  I suggest make it a relative "struct timespec
> > *" (more futureproof that timeval).  It would make sense to split the
> > interface into futex_down and futex_up syuscalls, since futex_up
> > doesn't need a timeout arg, but I haven't for the moment.
> 
> 	Why waste a syscall?  The user is going to be using a library
> wrapper.  They don't have to know that futex_up() calls sys_futex(futex,
> FUTEX_UP, NULL);

My bad.  There was a mistake in the patch (ie. I didn't actually do
this).

OTOH, shades of fcntl!  Syscalls are not "wasted": one for every
fundamental operation makes *sense*.  If I were doing it with timeouts
from scratch, I'd definitely have done two syscalls.  As it is, the
"op" arg gives us a chance for more overloading in future.

Hope that clarifies,
Rusty.
--
  Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

Re: [PATCH] Re: futex and timeouts

[Hubertus Franke]

On Friday 15 March 2002 01:08 am, Joel Becker wrote:
> On Fri, Mar 15, 2002 at 04:39:50PM +1100, Rusty Russell wrote:
> > Yep, sorry, my mistake.  I suggest make it a relative "struct timespec
> > *" (more futureproof that timeval).  It would make sense to split the
> > interface into futex_down and futex_up syuscalls, since futex_up
> > doesn't need a timeout arg, but I haven't for the moment.
>
> 	Why waste a syscall?  The user is going to be using a library
> wrapper.  They don't have to know that futex_up() calls sys_futex(futex,
> FUTEX_UP, NULL);
>
> Joel

I agree with that, only for the reason that we are getting scarce on 
syscall nubmers. Is 256-delta the max ?
On the other hand, it requires to always push 2 more arguments
(operand and useless parameter).

One thing to consider is that many don't want to use libraries.
They want to inline, which would result only in a few instruction.

What I would like to see is an interface that lets me pass optional 
parameters to the syscall interface, so I can call with different number
of parameters.

-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)

Re: [PATCH] Re: futex and timeouts

[Joel Becker]

On Fri, Mar 15, 2002 at 10:16:02AM -0500, Hubertus Franke wrote:
> > 	Why waste a syscall?  The user is going to be using a library
> > wrapper.  They don't have to know that futex_up() calls sys_futex(futex,
> > FUTEX_UP, NULL);
> 
> I agree with that, only for the reason that we are getting scarce on 
> syscall nubmers. Is 256-delta the max ?

	This was my impression, and why I called it "wasting" a syscall.
On architectures where syscall numbers or handles are unlimited, of
course there is no reason to keep it to one syscall.

> One thing to consider is that many don't want to use libraries.
> They want to inline, which would result only in a few instruction.

	Inlined you only take the penalty from the argument pushes.  You
still have to go through the motions of checking whether you can
get/release the lock in userspace.

> What I would like to see is an interface that lets me pass optional 
> parameters to the syscall interface, so I can call with different number
> of parameters.

	Is this to lock multiple futexes "atomically"?  If we are
looking for a fast path stack-wise, this seems extra work.

Joel

-- 

"Friends may come and go, but enemies accumulate." 
        - Thomas Jones

			http://www.jlbec.org/
			jlbec@evilplan.org

Re: [PATCH] Re: futex and timeouts

[Hubertus Franke]

On Friday 15 March 2002 11:04 am, Joel Becker wrote:
> On Fri, Mar 15, 2002 at 10:16:02AM -0500, Hubertus Franke wrote:
> > > 	Why waste a syscall?  The user is going to be using a library
> > > wrapper.  They don't have to know that futex_up() calls
> > > sys_futex(futex, FUTEX_UP, NULL);
> >
> > I agree with that, only for the reason that we are getting scarce on
> > syscall nubmers. Is 256-delta the max ?
>
> 	This was my impression, and why I called it "wasting" a syscall.
> On architectures where syscall numbers or handles are unlimited, of
> course there is no reason to keep it to one syscall.
>
> > One thing to consider is that many don't want to use libraries.
> > They want to inline, which would result only in a few instruction.
>
> 	Inlined you only take the penalty from the argument pushes.  You
> still have to go through the motions of checking whether you can
> get/release the lock in userspace.
>
> > What I would like to see is an interface that lets me pass optional
> > parameters to the syscall interface, so I can call with different number
> > of parameters.
>
> 	Is this to lock multiple futexes "atomically"?  If we are
> looking for a fast path stack-wise, this seems extra work.
>
> Joel

No, take for example...

syscall3(int,futex,int,op, struct futex*, futex, int opt_arg);

I will be always forced by the compiler (-Wall) to supply 3 arguments even 
as in the case of "no time out desired" I have to push a 3rd meaningless 
optional argument on the stack.


-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)

Re: [PATCH] Re: futex and timeouts

[Joel Becker]

On Fri, Mar 15, 2002 at 01:59:38PM -0500, Hubertus Franke wrote:
> > > What I would like to see is an interface that lets me pass optional
> > > parameters to the syscall interface, so I can call with different number
> > > of parameters.
> >
> > 	Is this to lock multiple futexes "atomically"?  If we are
> > looking for a fast path stack-wise, this seems extra work.
> 
> No, take for example...
> 
> syscall3(int,futex,int,op, struct futex*, futex, int opt_arg);

	Oh, I totally misparsed your statement.  I thought you meant you
wanted a vararg sys_futex(), not a smarter _syscall() :-)

Joel

-- 

Life's Little Instruction Book #347

	"Never waste the oppourtunity to tell someone you love them."

			http://www.jlbec.org/
			jlbec@evilplan.org

Re: [Lse-tech] Re: [PATCH] Re: futex and timeouts

[george anzinger]

Joel Becker wrote:
> 
> On Fri, Mar 15, 2002 at 01:59:38PM -0500, Hubertus Franke wrote:
> > > > What I would like to see is an interface that lets me pass optional
> > > > parameters to the syscall interface, so I can call with different number
> > > > of parameters.
> > >
> > >     Is this to lock multiple futexes "atomically"?  If we are
> > > looking for a fast path stack-wise, this seems extra work.
> >
> > No, take for example...
> >
> > syscall3(int,futex,int,op, struct futex*, futex, int opt_arg);
> 
I don't think there is anything "broken" in defining more than one
syscall stub to the same system call, each with a different parameter
count (or completely different arguments).  The call code will need to
be able to figure it out, but there is nothing in the way as far as
doing it.

-g

> --
> 
> Life's Little Instruction Book #347
> 
>         "Never waste the oppourtunity to tell someone you love them."
> 
>                         http://www.jlbec.org/
>                         jlbec@evilplan.org
> 
> _______________________________________________
> Lse-tech mailing list
> Lse-tech@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/lse-tech

-- 
George           george@mvista.com
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Real time sched: http://sourceforge.net/projects/rtsched/

Re: [Lse-tech] Re: [PATCH] Re: futex and timeouts

[Hubertus Franke]

On Friday 15 March 2002 08:12 pm, george anzinger wrote:
> Joel Becker wrote:
> > On Fri, Mar 15, 2002 at 01:59:38PM -0500, Hubertus Franke wrote:
> > > > > What I would like to see is an interface that lets me pass optional
> > > > > parameters to the syscall interface, so I can call with different
> > > > > number of parameters.
> > > >
> > > >     Is this to lock multiple futexes "atomically"?  If we are
> > > > looking for a fast path stack-wise, this seems extra work.
> > >
> > > No, take for example...
> > >
> > > syscall3(int,futex,int,op, struct futex*, futex, int opt_arg);
>
> I don't think there is anything "broken" in defining more than one
> syscall stub to the same system call, each with a different parameter
> count (or completely different arguments).  The call code will need to
> be able to figure it out, but there is nothing in the way as far as
> doing it.
>
> -g
>

Ofcourse, no difficulties here, but no convenient way either, as the 
__NR_futex is automatically used.

-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)