down_timeout

down_timeout

[Matthew Wilcox]

[l-k people, skip to the bottom, that's where down_timeout is]

On Fri, Oct 03, 2003 at 04:37:53PM +0400, Yury Umanets wrote:
> Thus, @quantum_ms will be calculated longer for shorter HZ and this is 
> definitelly not good in my opinion. Am I right?

You're right, but for the wrong reason.  This code is pretty inaccurate
as it's relying on the result of integer divides.  This code should
work better (disclaimer: compiled, not tested):

Index: drivers/acpi/osl.c
===================================================================
RCS file: /var/cvs/linux-2.6/drivers/acpi/osl.c,v
retrieving revision 1.3
diff -u -p -r1.3 osl.c
--- drivers/acpi/osl.c	23 Aug 2003 02:46:37 -0000	1.3
+++ drivers/acpi/osl.c	3 Oct 2003 14:02:44 -0000
@@ -827,7 +827,6 @@ acpi_os_wait_semaphore(
 {
 	acpi_status		status = AE_OK;
 	struct semaphore	*sem = (struct semaphore*)handle;
-	int			ret = 0;
 
 	ACPI_FUNCTION_TRACE ("os_wait_semaphore");
 
@@ -842,56 +841,28 @@ acpi_os_wait_semaphore(
 	if (in_atomic())
 		timeout = 0;
 
-	switch (timeout)
-	{
-		/*
-		 * No Wait:
-		 * --------
-		 * A zero timeout value indicates that we shouldn't wait - just
-		 * acquire the semaphore if available otherwise return AE_TIME
-		 * (a.k.a. 'would block').
-		 */
-		case 0:
-		if(down_trylock(sem))
-			status = AE_TIME;
-		break;
-
-		/*
-		 * Wait Indefinitely:
-		 * ------------------
-		 */
-		case ACPI_WAIT_FOREVER:
+	if (timeout == ACPI_WAIT_FOREVER) {
 		down(sem);
-		break;
-
-		/*
-		 * Wait w/ Timeout:
-		 * ----------------
-		 */
-		default:
-		// TODO: A better timeout algorithm?
-		{
-			int i = 0;
-			static const int quantum_ms = 1000/HZ;
-
+	} else if (down_trylock(sem) == 0) {
+		/* Success, do nothing */
+	} else {
+		long now = jiffies;
+		int ret = 1;
+		while (jiffies < now + timeout * HZ) {
+			current->state = TASK_INTERRUPTIBLE;
+			schedule_timeout(1);
 			ret = down_trylock(sem);
-			for (i = timeout; (i > 0 && ret < 0); i -= quantum_ms) {
-				current->state = TASK_INTERRUPTIBLE;
-				schedule_timeout(1);
-				ret = down_trylock(sem);
-			}
-	
-			if (ret != 0)
-				status = AE_TIME;
+			if (!ret)
+				break;
 		}
-		break;
+		if (ret)
+			status = AE_TIME;
 	}
 
 	if (ACPI_FAILURE(status)) {
 		ACPI_DEBUG_PRINT ((ACPI_DB_ERROR, "Failed to acquire semaphore[%p|%d|%d], %s\n", 
 			handle, units, timeout, acpi_format_exception(status)));
-	}
-	else {
+	} else {
 		ACPI_DEBUG_PRINT ((ACPI_DB_MUTEX, "Acquired semaphore[%p|%d|%d]\n", handle, units, timeout));
 	}
 

[l-k people, this is the interesting bit]

It's still not great because it doesn't preserve ordering.  down_timeout()
would be a much better primitive.  We have down_interruptible() which
could be used for this purpose.  Something like (completely uncompiled):

/* Returns -EINTR if the timeout expires */
int down_timeout(struct semaphore *sem, long timeout)
{
	struct timer_list timer;
	int result;

	init_timer(&timer);
	timer.expires = timeout + jiffies;
	timer.data = (unsigned long) current;
	timer.function = process_timeout;

	add_timer(&timer);
	result = down_interruptible(sem);
	del_timer_sync(&timer);

	return result;
}

(This would have to go in kernel/timer.c as that's where process_timeout
lives).

-- 
"It's not Hollywood.  War is real, war is primarily not about defeat or
victory, it is about death.  I've seen thousands and thousands of dead bodies.
Do you think I want to have an academic debate on this subject?" -- Robert Fisk

Re: down_timeout

[Andrew Morton]

Matthew Wilcox <willy@debian.org> wrote:
>
> /* Returns -EINTR if the timeout expires */
> int down_timeout(struct semaphore *sem, long timeout)
> {
> 	struct timer_list timer;
> 	int result;
> 
> 	init_timer(&timer);
> 	timer.expires = timeout + jiffies;
> 	timer.data = (unsigned long) current;
> 	timer.function = process_timeout;
> 
> 	add_timer(&timer);
> 	result = down_interruptible(sem);
> 	del_timer_sync(&timer);
> 
> 	return result;
> }

down_interruptible() will only break out if signal_pending(current), so the
wakeup-on-expiry here will not work as desired.

New per-arch primitives would be needed to implement this, I think.

RE: down_timeout

[Grover, Andrew]

> From: linux-kernel-owner@vger.kernel.org 
> [mailto:linux-kernel-owner@vger.kernel.org] On Behalf Of 
> Matthew Wilcox
> It's still not great because it doesn't preserve ordering.  
> down_timeout()
> would be a much better primitive.  We have down_interruptible() which
> could be used for this purpose.  Something like (completely 
> uncompiled):

Yeah we proposed this 2 years ago and someone (don't remember who) shot
us down.

Regards -- Andy

Re: down_timeout

[Ingo Oeser]

Hi Andrew,

On Friday 03 October 2003 20:03, Grover, Andrew wrote:
> > From: linux-kernel-owner@vger.kernel.org
> > [mailto:linux-kernel-owner@vger.kernel.org] On Behalf Of
> > Matthew Wilcox
> > It's still not great because it doesn't preserve ordering.
> > down_timeout()
> > would be a much better primitive.  We have down_interruptible() which
> > could be used for this purpose.  Something like (completely
> > uncompiled):
>
> Yeah we proposed this 2 years ago and someone (don't remember who) shot
> us down.

It was me.

Reason: 
	I misunderstood your suggestion down_timeout() as "down and hold
	a semaphore until timeout" instead of "try until timeout to get
	the semaphore". I suggested using waitqueues for this.

But now that I understand, what you really want, I agree that this is
very useful and also agree that the kernel should provide it.

I don't think that I prevented it from being accepted, but my opinion
about it might had have the wrong influence.

I'm really sorry, that this simple communication problem caused you,
the ACPI development and users such a big pain.

PS: And I still think that semaphores with a maximum hold time are a bad
    idea in the linux kernel. But this is just *my* opinion ;-)

Regards

Ingo Oeser

RE: down_timeout

[Moore, Robert]

I see this as the kind of function that should be implemented within the
semaphore interface itself.  Very simple - Just wake me up when either 1) I
get the semaphore, or 2) I timed out.

A single implementation saves everyone from attempting to implement this
over and over and over.

Bob


		-----Original Message-----
		From:	Ingo Oeser
[mailto:ingo.oeser@informatik.tu-chemnitz.de]
		Sent:	Wednesday, April 25, 2001 4:49 PM
		To:	Grover, Andrew
		Cc:	'linux-kernel@vger.kernel.org'; Moore, Robert
		Subject:	Re: down_timeout

		On Wed, Apr 25, 2001 at 04:21:22PM -0700, Grover, Andrew
wrote:
		> It seems like we need to implement down_timeout (and
		> down_timeout_interruptible) to fully flesh out the
semaphore implementation.
		> It is difficult and inefficient to emulate this using
wrapper functions, as
		> far as I can see.
		> 
		> Seems like this is a fairly standard interface to have for
OS semaphores. We
		> have a prototype implementation, and could contribute
this, if desired.
		> 
		> Thoughts?

		Sure you can't implement this via waitqueues? semaphores use
them
		internally anyway.

		I use this for interrupt or polling based waiting:


		/* IO polling waits */
		/* Timeout after this amount of jiffies */
		#define IO_POLL_TIMEOUT (HZ) 	
		/* Split timeout while polling into chunks of that many
jiffies */
		#define IO_POLL_SPLIT 	2

		/* generic interrupt based wait with timeouts! */
		#define __wait_event_timeout_int(wq, condition, timeout,
ret) \
			do { \
				struct wait_queue __wait; \
				signed long __expire=timeout; \
				__wait.task=current; \
				add_wait_queue(wq, &__wait); \
				for (;;) { \
					current->state=TASK_UNINTERRUPTIBLE;
\
					mb(); \
					if (condition) break; \
					__expire=schedule_timeout(__expire);
\
					if (__expire == 0) {  \
						ret=-ETIMEDOUT; \
						break; \
					} \
				} \
				current->state = TASK_RUNNING; \
				remove_wait_queue(wq, &__wait); \
			} while (0)

		/* polling wait, if we shouldn't use interrupts for this */
		#define __wait_event_timeout_poll(wq, condition, timeout,
ret) \
			do { \
				unsigned int __tries=0; \
				unsigned int __maxtry=timeout /
IO_POLL_SPLIT; \
				do { \
					schedule_timeout(IO_POLL_SPLIT); \
					if (condition) \
						break; \
				} while (++__tries < __maxtry); \
				if (__tries == __maxtry && !condition) \
					ret=-ETIMEDOUT; \
			} while (0)
			
		#ifdef INTS_ARE_CHEAP
		#define __wait_event_timeout(wq, condition, timeout, ret) \
			__wait_event_timeout_int(wq, condition, timeout,
ret)
		#else /* INTS_ARE_CHEAP */
		#define __wait_event_timeout(wq, condition, timeout, ret) \
			__wait_event_timeout_poll(wq, condition, timeout,
ret)
		#endif /* INTS_ARE_CHEAP */

		#define wait_event_timeout(wq, condition, timeout, ret)	\
			do { \
				if (condition) \
					break; \
				__wait_event_timeout(wq, condition, timeout,
ret); \
			} while (0)


		What about that?

		Use it just as you use wait_event() but check for -ETIMEDOUT
as
		value in ret.

		Regards

		Ingo Oeser
		-- 
		10.+11.03.2001 - 3. Chemnitzer LinuxTag
<http://www.tu-chemnitz.de/linux/tag>
		         <<<<<<<<<<<<     been there and had much fun
>>>>>>>>>>>>

down_timeout

[Grover, Andrew]

It seems like we need to implement down_timeout (and
down_timeout_interruptible) to fully flesh out the semaphore implementation.
It is difficult and inefficient to emulate this using wrapper functions, as
far as I can see.

Seems like this is a fairly standard interface to have for OS semaphores. We
have a prototype implementation, and could contribute this, if desired.

Thoughts?

Regards -- Andy

Re: down_timeout

[Ingo Oeser]

On Wed, Apr 25, 2001 at 04:21:22PM -0700, Grover, Andrew wrote:
> It seems like we need to implement down_timeout (and
> down_timeout_interruptible) to fully flesh out the semaphore implementation.
> It is difficult and inefficient to emulate this using wrapper functions, as
> far as I can see.
> 
> Seems like this is a fairly standard interface to have for OS semaphores. We
> have a prototype implementation, and could contribute this, if desired.
> 
> Thoughts?

Sure you can't implement this via waitqueues? semaphores use them
internally anyway.

I use this for interrupt or polling based waiting:


/* IO polling waits */
/* Timeout after this amount of jiffies */
#define IO_POLL_TIMEOUT (HZ) 	
/* Split timeout while polling into chunks of that many jiffies */
#define IO_POLL_SPLIT 	2

/* generic interrupt based wait with timeouts! */
#define __wait_event_timeout_int(wq, condition, timeout, ret) \
	do { \
		struct wait_queue __wait; \
		signed long __expire=timeout; \
		__wait.task=current; \
		add_wait_queue(wq, &__wait); \
		for (;;) { \
			current->state=TASK_UNINTERRUPTIBLE; \
			mb(); \
			if (condition) break; \
			__expire=schedule_timeout(__expire); \
			if (__expire == 0) {  \
				ret=-ETIMEDOUT; \
				break; \
			} \
		} \
		current->state = TASK_RUNNING; \
		remove_wait_queue(wq, &__wait); \
	} while (0)

/* polling wait, if we shouldn't use interrupts for this */
#define __wait_event_timeout_poll(wq, condition, timeout, ret) \
	do { \
		unsigned int __tries=0; \
		unsigned int __maxtry=timeout / IO_POLL_SPLIT; \
		do { \
			schedule_timeout(IO_POLL_SPLIT); \
			if (condition) \
				break; \
		} while (++__tries < __maxtry); \
		if (__tries == __maxtry && !condition) \
			ret=-ETIMEDOUT; \
	} while (0)
	
#ifdef INTS_ARE_CHEAP
#define __wait_event_timeout(wq, condition, timeout, ret) \
	__wait_event_timeout_int(wq, condition, timeout, ret)
#else /* INTS_ARE_CHEAP */
#define __wait_event_timeout(wq, condition, timeout, ret) \
	__wait_event_timeout_poll(wq, condition, timeout, ret)
#endif /* INTS_ARE_CHEAP */

#define wait_event_timeout(wq, condition, timeout, ret)	\
	do { \
		if (condition) \
			break; \
		__wait_event_timeout(wq, condition, timeout, ret); \
	} while (0)


What about that?

Use it just as you use wait_event() but check for -ETIMEDOUT as
value in ret.

Regards

Ingo Oeser
-- 
10.+11.03.2001 - 3. Chemnitzer LinuxTag <http://www.tu-chemnitz.de/linux/tag>
         <<<<<<<<<<<<     been there and had much fun   >>>>>>>>>>>>