[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

[PATCH] New condition variable design: OpenOffice works



This patch makes OpenOffice work by changing the condition variable
design.
The problem with the current one is that if a thread does
pthread_cond_signal(cv); pthread_cond_wait(cv);, it is possible that
the signal will wake the wait done after it.
Also note that SUSv3 says that threads currently waiting should be
affected by signals, not ones that wait after the signal.

The new design fixes the problem by the changing the way nr_wakers is
handled:
1. __lll_cond_wake takes its value and wakes up when it notices a
change
2. __lll_cond_signal increments nr_wakers

The fact that nr_wakers is never decremented causes problems with
overflow: this is solved by waking up all threads waiting on the cv,
waiting until nr_sleepers == 0 and finally resetting nr_wakers to 0.

Anyway, DESIGN-condvar.txt is updated with the details.

Note that while apparently it works, it is not unlikely that the
assembly code contains errors, so please check it.

--- nptl/DESIGN-condvar.txt~	2002-10-08 22:32:33.000000000 +0200
+++ nptl/DESIGN-condvar.txt	2002-11-02 02:25:58.000000000 +0100
@@ -25,49 +26,56 @@ struct pthread_cond_t {
 
 cond_wait_timeout(cv, mutex, timeout):
 {
-   lll_lock(cv->lock);
-   mutex_unlock(mutex);
-
-   cv->nr_sleepers++;
-   for (;;) {
-
-       if (cv->nr_wakers) {
-           cv->nr_wakers--;
-           break;
-       }
-       val = cv->nr_wakers;
-
-       lll_unlock(cv->lock);
+   unsigned ournr_waiters;
+   lll_lock(cv->lock);   
+   ournr_waiters = cv->nr_waiters;
 
-       ret = FUTEX WAIT (cv->nr_wakers, val, timeout)
+   ++cv->nr_sleepers;
+   lll_unlock(cv->lock);
 
-       lll_lock(cv->lock);
+   mutex_unlock(mutex);
+      
+   while((*(volatile int*)&cv->nr_waiters != ourtime))
+   {
+       ret = FUTEX WAIT (cv->nr_waiters, ournr_waiters, timeout)
 
        if (ret == TIMEOUT)
          break;
        ret = 0;
    }
-   if (!--cv->nr_sleepers)
-     cv->nr_wakers = 0; /* no memory of wakeups */
-   lll_unlock(cv->lock);
+   if (atomic_decrement_and_test(&cv->nr_sleepers))
+   {
+	if(*(volatile signed*)&cv->nr_waiters < 0)
+		FUTEX WAKE (cv->nr_sleepers, 1);
+   }
    mutex_lock(mutex);
 
    return ret;
 }
 
+__cond_reset(cv)
+{
+	unsigned sleepers;
+	FUTEX WAKE (cv->nr_waiters, ALL_THREADS);
+	while((sleepers = cv->nr_sleepers))
+		FUTEX WAIT (cv->nr_sleepers, sleepers);
+	cv->nr_waiters = 0;
+}
+
 cond_signal(cv)
 {
    int do_wakeup = 0;
 
    lll_lock(cv->lock);
    if (cv->nr_sleepers) {
-     if (!++cv->nr_wakers) /* overflow detection for the nutcase */
-       cv->nr_wakers = ALL_THREADS;
-     do_wakeup = 1;
+     if((signed)++cv->nr_waiters < 0)
+       __cond_reset(cv);
+     else
+       do_wakeup = 1;
    }
    lll_unlock(cv->lock);
    if (do_wakeup)
-     FUTEX WAKE (cv->nr_wakers, 1)
+     FUTEX WAKE (cv->nr_waiters, 1)
 }
 
 cond_broadcast(cv)
@@ -76,12 +84,14 @@ cond_broadcast(cv)
 
    lll_lock(cv->lock);
    if (cv->nr_sleepers) {
-     cv->nr_wakers |= ALL_THREADS;
-     do_wakeup = 1;
+     if((signed)++cv->nr_waiters < 0)
+       __cond_reset(cv);   
+     else
+       do_wakeup = 1;
    }
    lll_unlock(cv->lock);
    if (do_wakeup)
-     FUTEX WAKE (cv->nr_wakers, ALL_THREADS);
+     FUTEX WAKE (cv->nr_waiters, ALL_THREADS);
 }
 
 weaknesses of the implementation:
--- nptl/pthread_cond_wait.c~	2002-10-08 23:05:24.000000000 +0200
+++ nptl/pthread_cond_wait.c	2002-11-02 00:26:25.000000000 +0100
@@ -49,13 +49,6 @@ pthread_cond_wait (cond, mutex)
   /* The actual conditional variable implementation.  */
   lll_cond_wait (cond);
 
-  if (--cond->__data.__nr_sleepers == 0)
-    /* Forget about the current wakeups now that they are done.  */
-    cond->__data.__nr_wakers = 0;
-
-  /* Lose the condvar lock.  */
-  lll_mutex_unlock (cond->__data.__lock);
-
   /* We have to get the mutex before returning.  */
   err = pthread_mutex_lock (mutex);
 
--- nptl/pthread_cond_timedwait.c~	2002-10-09 00:40:27.000000000 +0200
+++ nptl/pthread_cond_timedwait.c	2002-11-02 01:21:16.000000000 +0100
@@ -51,13 +51,6 @@ pthread_cond_timedwait (cond, mutex, abs
   /* The actual conditional variable implementation.  */
   result = lll_cond_timedwait (cond, abstime);
 
-  if (--cond->__data.__nr_sleepers == 0)
-    /* Forget about the current wakeups now that they are done.  */
-    cond->__data.__nr_wakers = 0;
-
-  /* Lose the condvar lock.  */
-  lll_mutex_unlock (cond->__data.__lock);
-
   /* We have to get the mutex before returning.  */
   err = pthread_mutex_lock (mutex);
   if (err != 0)
--- nptl/sysdeps/unix/sysv/linux/i386/i486/lowlevelcond.S~	2002-09-19 11:57:30.000000000 +0200
+++ nptl/sysdeps/unix/sysv/linux/i386/i486/lowlevelcond.S	2002-11-02 02:26:26.000000000 +0100
@@ -50,44 +50,51 @@ __lll_cond_wait:
 	pushl	%ebx
 
 	xorl	%esi, %esi
+	xorl	%ecx, %ecx	/* movl $FUTEX_WAIT, %ecx */
 
+	/* get nr_wakers */
 	leal	cond_nr_wakers(%eax), %ebx
+	movl	(%ebx), %edx
 
-4:	movl	(%ebx), %edx
-	testl	%edx, %edx
-	jne	1f
-
+	/* drop lock */
 	LOCK
 	decl	cond_lock-cond_nr_wakers(%ebx)
-	jne	2f
-
-3:	xorl	%ecx, %ecx
-	movl	$SYS_futex, %eax
+	jne	3f
+	
+1:	movl	$SYS_futex, %eax
 	int	$0x80
 
-	movl	$1, %eax
-	LOCK
-	xaddl	%eax, cond_lock-cond_nr_wakers(%ebx)
-	testl	%eax, %eax
-	je	4b
+	/* loop if no wakeup */
+	cmpl	%edx, (%ebx)
+	je	1b
 
-	leal	cond_lock-cond_nr_wakers(%ebx), %ecx
-	/* Preserves %ebx, %edx, %edi, %esi.  */
-	call	__lll_mutex_lock_wait
-	jmp	4b
+	/* decrement nr_sleepers */
+5:	LOCK
+	decl	cond_nr_sleepers-cond_nr_wakers(%ebx)
+	jne 2f
 
-1:	decl	(%ebx)
+	cmpl	$0, (%ebx)
+	js 4f
 
-	popl	%ebx
+2:	popl	%ebx
 	popl	%esi
 	ret
 
-2:	leal	cond_lock-cond_nr_wakers(%ebx), %eax
+	/* drop lock: wakeup */
+3:	leal	cond_lock-cond_nr_wakers(%ebx), %eax
 	/* Preserves %ebx, %ecx, %edx, %edi, %esi.  */
 	call	__lll_mutex_unlock_wake
-	jmp	3b
-	.size	__lll_cond_wait,.-__lll_cond_wait
+	jmp	1b
 
+	/* decrement nr_sleepers: wakeup resetter */
+4:	addl	$cond_nr_sleepers-cond_nr_wakers, %ebx
+	movl	$FUTEX_WAKE, %ecx
+	movl	%ecx, %edx	/* movl $1, %edx */
+	movl	$SYS_futex, %eax
+	int	$0x80
+	jmp 2b
+	.size	__lll_cond_wait,.-__lll_cond_wait	
+		
 
 	.global	__lll_cond_timedwait
 	.type	__lll_cond_timedwait,@function
@@ -96,7 +103,7 @@ __lll_cond_wait:
 __lll_cond_timedwait:
 	/* Check for a valid timeout value.  */
 	cmpl	$1000000000, 4(%edx)
-	jae	1f
+	jae	7f
 
 	pushl	%ebp
 	pushl	%edi
@@ -106,19 +113,19 @@ __lll_cond_timedwait:
 	/* Stack frame for the timespec and timeval structs.  */
 	subl	$8, %esp
 
+	/* get nr_wakers */
 	leal	cond_nr_wakers(%eax), %ebp	/* cond */
 	movl	%edx, %edi			/* timeout */
+	
+	movl	(%ebp), %esi
 
-9:	movl	(%ebp), %esi
-	testl	%esi, %esi
-	jne	5f
-
+	/* drop lock */	
 	LOCK
 	decl	cond_lock-cond_nr_wakers(%ebp)
-	jne	6f
+	jne	3f
 
 	/* Get current time.  */
-7:	movl	%esp, %ebx
+1:	movl	%esp, %ebx
 	xorl	%ecx, %ecx
 	movl	$SYS_gettimeofday, %eax
 	int	$0x80
@@ -131,11 +138,11 @@ __lll_cond_timedwait:
 	movl	4(%edi), %edx
 	subl	(%esp), %ecx
 	subl	%eax, %edx
-	jns	3f
+	jns	8f
 	addl	$1000000000, %edx
 	decl	%ecx
-3:	testl	%ecx, %ecx
-	js	4f		/* Time is already up.  */
+8:	testl	%ecx, %ecx
+	js	6f		/* Time is already up.  */
 
 	movl	%ecx, (%esp)	/* Store relative timeout.  */
 	movl	%edx, 4(%esp)
@@ -146,22 +153,23 @@ __lll_cond_timedwait:
 	movl	$SYS_futex, %eax
 	int	$0x80
 
-	movl	%eax, %edx
+	cmpl	$-ETIMEDOUT, %eax
+	je	6f
 
-	movl	$1, %eax
-	LOCK
-	xaddl	%eax, cond_lock-cond_nr_wakers(%ebp)
-	testl	%eax, %eax
-	jne	8f
+	movl	%edx, %esi
+	
+	cmpl	%edx, (%ebx)
+	je	1b
 
-	cmpl	$-ETIMEDOUT, %edx
-	jne	9b
+	xorl	%eax, %eax	
 
-4:	movl	$ETIMEDOUT, %eax
-	jmp	2f
+	/* decrement nr_sleepers */
+5:	LOCK
+	decl	cond_nr_sleepers-cond_nr_wakers(%ebp)
+	jne	2f
 
-5:	decl	(%ebp)
-	xorl	%eax, %eax
+	cmpl	$0, (%ebp)
+	js	4f
 
 2:	addl	$8, %esp
 	popl	%ebx
@@ -170,20 +178,29 @@ __lll_cond_timedwait:
 	popl	%ebp
 	ret
 
-6:	leal	cond_lock-cond_nr_wakers(%ebp), %eax
+6:	movl	$ETIMEDOUT, %eax
+	jmp	5b
+
+	/* drop lock: wakeup */
+3:	leal	cond_lock-cond_nr_wakers(%ebp), %eax
 	/* Preserves %ebx, %ecx, %edx, %edi, %esi.  */
 	call	__lll_mutex_unlock_wake
-	jmp	7b
-
-8:	leal	cond_lock-cond_nr_wakers(%ebp), %ecx
-	/* Preserves %ebx, %edx, %edi, %esi.  */
-	call	__lll_mutex_lock_wait
-	jmp	5b
+	jmp	1b
 
-1:	movl	$EINVAL, %eax
+7:	movl	$EINVAL, %eax
 	ret
-	.size	__lll_cond_timedwait,.-__lll_cond_timedwait
 
+	/* decrement nr_sleepers: wakeup resetter */
+4:	movl	%eax, (%esp)
+	xorl	%esi, %esi
+	leal	cond_nr_sleepers-cond_nr_wakers(%ebp), %ebx
+	movl	$FUTEX_WAKE, %ecx
+	movl	%ecx, %edx	/* movl $1, %edx */
+	movl	$SYS_futex, %eax
+	int	$0x80
+	movl	(%esp), %eax
+	jmp	2b
+	.size	__lll_cond_timedwait,.-__lll_cond_timedwait	
 
 	.global	__lll_cond_wake
 	.type	__lll_cond_wake,@function
@@ -192,6 +209,7 @@ __lll_cond_timedwait:
 __lll_cond_wake:
 	pushl	%esi
 	pushl	%ebx
+	xorl	%esi, %esi
 
 	movl	%eax, %ebx
 
@@ -206,10 +224,9 @@ __lll_cond_wake:
 	je	3f
 
 	incl	(%ebx)
-	jz	5f
+	js	__lll_cond_reset
 
 6:	movl	$FUTEX_WAKE, %ecx
-	xorl	%esi, %esi
 	movl	%ecx, %edx	/* movl $1, %edx */
 	movl	$SYS_futex, %eax
 	int	$0x80
@@ -228,9 +245,6 @@ __lll_cond_wake:
 1:	movl	%ebx, %ecx
 	call	__lll_mutex_lock_wait
 	jmp	2b
-
-5:	movl	$0x80000000, (%ebx)
-	jmp	6b
 	.size	__lll_cond_wake,.-__lll_cond_wake
 
 
@@ -243,7 +257,8 @@ __lll_cond_broadcast:
 	pushl	%ebx
 
 	movl	%eax, %ebx
-	movl	$0x8000000, %edx
+	movl	$0x80000000, %edx
+	xorl	%esi, %esi
 
 	movl	$1, %eax
 	LOCK
@@ -255,10 +270,10 @@ __lll_cond_broadcast:
 	cmpl	$0, cond_nr_sleepers-cond_nr_wakers(%ebx)
 	je	3f
 
-	orl	%edx, (%ebx)
+	incl	(%ebx)
+	js	__lll_cond_reset
 
 6:	movl	$FUTEX_WAKE, %ecx
-	xorl	%esi, %esi
 	movl	$SYS_futex, %eax
 	int	$0x80
 
@@ -277,3 +292,31 @@ __lll_cond_broadcast:
 	call	__lll_mutex_lock_wait
 	jmp	2b
 	.size	__lll_cond_broadcast,.-__lll_cond_broadcast
+
+
+# this is a named label, not an externally usable function
+__lll_cond_reset:
+	movl	$0x80000000, %edx	
+	movl	$FUTEX_WAKE, %ecx
+	xorl	%esi, %esi
+	movl	$SYS_futex, %eax
+	int	$0x80
+
+	addl	$cond_nr_sleepers-cond_nr_wakers, %ebx
+	movl	(%ebx), %edx
+	testl	%edx, %edx
+	je	2f
+
+	xorl	%ecx, %ecx	/* movl $FUTEX_WAIT, %ecx */	
+	
+1:	movl	$SYS_futex, %eax
+	int	$0x80
+
+	movl	(%ebx), %edx
+	testl	%edx, %edx
+	jne	1b
+
+2:	movl	$0, cond_nr_wakers-cond_nr_sleepers(%ebx)
+	popl %ebx
+	popl %esi
+	ret

Attachment: pgp00013.pgp
Description: PGP signature


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]