Re: [PATCH] optimization for sys_semtimedop() (was: Opening Day for OpenSolaris)

Re: [PATCH] optimization for sys_semtimedop() (was: Opening Day for OpenSolaris)

[Robert Gadsdon]

IANAL, but if this is from 'OpenSolaris sources' then surely it would be 
incompatible with the GPL?

Robert Gadsdon.

Manfred Spraul wrote:
> Hi,
> 
> semtimedop() performs a semaphore operation and if the operation cannot 
> be performed immediately, then the function blocks until the timeout 
> expires.
> The current Linux implementation loads the timeout immediately, even if 
> the operation doesn't block.
> As explained in the OpenSolaris sources, this is not needed. The 
> attached patch changes the Linux code.
> 
> The patch is trivial, but not tested. It shrinks the .text size by 32 
> bytes on x86.
> 
> -- 
>    Manfred
> 

[PATCH] optimization for sys_semtimedop() (was: Opening Day for OpenSolaris)

[Manfred Spraul]

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

Hi,

semtimedop() performs a semaphore operation and if the operation cannot 
be performed immediately, then the function blocks until the timeout 
expires.
The current Linux implementation loads the timeout immediately, even if 
the operation doesn't block.
As explained in the OpenSolaris sources, this is not needed. The 
attached patch changes the Linux code.

The patch is trivial, but not tested. It shrinks the .text size by 32 
bytes on x86.

--
    Manfred

[-- Attachment #2: patch-ipcsem-latetimeout --]
[-- Type: text/plain, Size: 3808 bytes --]

--- 2.6/ipc/sem.c	2005-06-14 19:01:23.000000000 +0200
+++ build-2.6/ipc/sem.c	2005-06-14 19:00:32.000000000 +0200
@@ -1056,13 +1056,12 @@
 	struct sem_undo *un;
 	int undos = 0, alter = 0, max;
 	struct sem_queue queue;
-	unsigned long jiffies_left = 0;
 
 	if (nsops < 1 || semid < 0)
 		return -EINVAL;
 	if (nsops > sc_semopm)
 		return -E2BIG;
-	if(nsops > SEMOPM_FAST) {
+	if (nsops > SEMOPM_FAST) {
 		sops = kmalloc(sizeof(*sops)*nsops,GFP_KERNEL);
 		if(sops==NULL)
 			return -ENOMEM;
@@ -1071,19 +1070,6 @@
 		error=-EFAULT;
 		goto out_free;
 	}
-	if (timeout) {
-		struct timespec _timeout;
-		if (copy_from_user(&_timeout, timeout, sizeof(*timeout))) {
-			error = -EFAULT;
-			goto out_free;
-		}
-		if (_timeout.tv_sec < 0 || _timeout.tv_nsec < 0 ||
-			_timeout.tv_nsec >= 1000000000L) {
-			error = -EINVAL;
-			goto out_free;
-		}
-		jiffies_left = timespec_to_jiffies(&_timeout);
-	}
 	max = 0;
 	for (sop = sops; sop < sops + nsops; sop++) {
 		if (sop->sem_num >= max)
@@ -1160,21 +1146,66 @@
 	current->state = TASK_INTERRUPTIBLE;
 	sem_unlock(sma);
 
-	if (timeout)
-		jiffies_left = schedule_timeout(jiffies_left);
-	else
+	if (timeout) {
+		/*
+		 * Neat trick mentioned in the OpenSolaris source
+		 * (but not implemented by them):
+		 * There is no need to load the timeout early, its sufficient
+		 * to load the timeout when we are about to block.
+		 * Unfortunately that makes error handling tricky:
+		 * Our request is already alive and another cpu
+		 * could fulfill it while we try to handle the error condition.
+		 * Solution: Behave as if a signal woke us up immediately
+		 * and replace the error code at the end.
+		 */
+		struct timespec _timeout;
+		if (copy_from_user(&_timeout, timeout, sizeof(*timeout))) {
+			error = -EFAULT;
+		} else if (_timeout.tv_sec < 0 || _timeout.tv_nsec < 0 ||
+			_timeout.tv_nsec >= 1000000000L) {
+			error = -EINVAL;
+		} else {
+			unsigned long jiffies_left;
+			jiffies_left = timespec_to_jiffies(&_timeout);
+			jiffies_left = schedule_timeout(jiffies_left);
+			if (jiffies_left)
+				error = -EAGAIN;
+			else
+				error = -EINTR;
+		}
+	} else {
 		schedule();
-
-	error = queue.status;
-	while(unlikely(error == IN_WAKEUP)) {
-		cpu_relax();
-		error = queue.status;
+		error = -EINTR;
 	}
 
-	if (error != -EINTR) {
-		/* fast path: update_queue already obtained all requested
-		 * resources */
-		goto out_free;
+	/*
+	 * lockless fast path:
+	 * If queue.status != -EINTR we were woken up by another semop().
+	 * But then update_queue removed us from the queue already,
+	 * we can/must exit immediately without trying to acquire the
+	 * semaphore lock.
+	 * There is no need for memory barriers: We only read
+	 * a single integer and use it as the return code. Thus
+	 * we use barrier() and copy the status code into a local
+	 * variable.
+	 */
+	{
+		int tmp;
+
+		tmp = queue.status;
+		while(unlikely(tmp == IN_WAKEUP)) {
+			cpu_relax();
+			tmp = queue.status;
+			barrier();
+		}
+		barrier();
+
+		if (tmp != -EINTR) {
+			/* fast path: update_queue already obtained all requested
+			 * resources */
+			error = tmp;
+			goto out_free;
+		}
 	}
 
 	sma = sem_lock(semid);
@@ -1185,22 +1216,16 @@
 		goto out_free;
 	}
 
-	/*
-	 * If queue.status != -EINTR we are woken up by another process
-	 */
-	error = queue.status;
-	if (error != -EINTR) {
-		goto out_unlock_free;
+	if (queue.status == -EINTR) {
+		/*
+		 * If an interrupt occurred we have to clean up the queue
+		 * ourself.
+		 */
+		remove_from_queue(sma,&queue);
+	} else {
+		error = queue.status;
 	}
 
-	/*
-	 * If an interrupt occurred we have to clean up the queue
-	 */
-	if (timeout && jiffies_left == 0)
-		error = -EAGAIN;
-	remove_from_queue(sma,&queue);
-	goto out_unlock_free;
-
 out_unlock_free:
 	sem_unlock(sma);
 out_free:

Re: [PATCH] optimization for sys_semtimedop() (was: Opening Day for OpenSolaris)

[Manfred Spraul]

Hi Robert,

>IANAL, but if this is from 'OpenSolaris sources' then surely it would be 
>incompatible with the GPL?
>
>  
>
The idea is from the OpenSolaris sources, the implementation is 
independant. Actually OpenSolaris doesn't contain an implementation at 
all, it just mentions the idea.

Jim: From my understanding of the CDDL, only a file that "contains any 
part of the Original Software" must be licensed under the CDDL, there 
are no restrictions (except possibly patents, but I assume that even the 
USPTO won't grant a patent on such a trivial idea) on using methods or 
ideas from OpenSolaris in software that uses other licenses.
Is that correct?

--
    Manfred

Re: [PATCH] optimization for sys_semtimedop() (was: Opening Day for OpenSolaris)

[Patrick Plattes]

On Wed, Jun 15, 2005 at 07:14:53AM +0200, Manfred Spraul wrote:
 
> Jim: From my understanding of the CDDL, only a file that "contains any 
> part of the Original Software" must be licensed under the CDDL, there 
> are no restrictions (except possibly patents, but I assume that even the 
> USPTO won't grant a patent on such a trivial idea) on using methods or 
> ideas from OpenSolaris in software that uses other licenses.
> Is that correct?

Hello,

Patch: The patch looks fine and compiles clean.

CDDL: What is the definition of 'part'? IMHO we need a debate how to
work with OpenSolaris ideas and the debate must me done by lawyers, 
not by kernel hacker.

Other: sem.c is hard to read - for me. Long functions and a lot of
gotos confusing me. is this only my problem or is it really hard to
understand?

cu
pp