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

Re: [PATCH] New condition variable design: OpenOffice works



Here is a completely untested optimized x86 assembly partial
implementation of a slightly different version of the design.

Here are the differences:
- The "algorithm" field is replaced by 4 byte fields containing the
value to be added before/after read/write. Note that, while occupying
32-bit, they only carry 2 bits of information like the algorithm (and
one of the 4 values is unusable)

- When performing reader unlocks, the implementation never wakes
readers. Waking them is not wrong, but is unnecessary

- nr_readers and writer are removed and writers is added and contains
the number of writers. Note that readers = writers ? 0 : write_blockers.

Furthermore no error checking is done: a separate debug library can be
used for that.


/* Copyright (C) 2002 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Contributed by Ulrich Drepper <drepper redhat com>, 2002.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <sysdep.h>

	.text

#define SYS_gettimeofday	__NR_gettimeofday
#define SYS_futex		240
#define FUTEX_WAIT		0
#define FUTEX_WAKE		1

#define EAGAIN		11
#define EDEADLK		35
#define ETIMEDOUT	110

/* Offsets in the pthread_rwlock_t structure.  */
#define MUTEX		0
#define WRITERS		4
#define READ_BLOCKERS	8
#define WRITE_BLOCKERS	12
#define READERS_QUEUED	16
#define WRITERS_QUEUED	20
#define MODE		24
#define READ_PRE_ADD	24
#define WRITE_PRE_ADD	25
#define READ_POST_ADD	26	
#define WRITE_POST_ADD	27			
#define UNUSED		28

#define FIRST_COME_FIRST_SERVED 0
#define READERS_RULE 1
#define WRITERS_RULE 0x100
	
#ifndef UP
# define LOCK lock
#else
# define LOCK
#endif


	.globl	__pthread_rwlock_rdlock
	.type	__pthread_rwlock_rdlock,@function
	.align	16
__pthread_rwlock_rdlock:
	movl	4(%esp), %ecx

	/* Get the lock.  */
	movl	$1, %eax
	LOCK
	xaddl	%eax, MUTEX(%ecx)
	testl	%eax, %eax
	jne	1f

2:	movl	READ_BLOCKERS(%ecx), %edx
	testl	%edx, %edx
	jne	4f

	incl	WRITE_BLOCKERS(%ecx)
	
	/* drop lock */
9:	LOCK
	decl	MUTEX(%ecx)
	jne	6f
7:
	xorl	%eax, %eax
	ret



4:	pushl	%ebx
	pushl	%esi
	xorl	%esi, %esi

	/* maybe block writers */			
	movzbl	READ_PRE_ADD(%ecx), %eax
	addl	%eax, WRITE_BLOCKERS(%ecx)

	incl	READERS_QUEUED(%ecx)

	leal	READ_BLOCKERS(%ecx), %ebx

	/* drop lock */
3:	LOCK
	decl	MUTEX-READ_BLOCKERS(%ebx)
	jne	10f

11:	movl	%esi, %ecx	/* movl $FUTEX_WAIT, %ecx */
	movl	$SYS_futex, %eax
	int	$0x80

	/* Reget the lock.  */
	movl	$1, %eax
	LOCK
	xaddl	%eax, MUTEX-READ_BLOCKERS(%ebx)
	testl	%eax, %eax
	jne	12f

12:	movl	(%ebx), %edx
	testl	%edx, %edx
	jne	3b

	decl	READERS_QUEUED-READ_BLOCKERS(%ebx)
			
	/* block writers if we didn't before */	
	movzbl	READ_POST_ADD-READ_BLOCKERS(%ebx), %eax
	addl	%eax, WRITE_BLOCKERS-READ_BLOCKERS(%ebx)

	leal	-READ_BLOCKERS(%ebx), %ecx
	
	popl	%esi
	popl	%ebx
	jmp	9b
	
	
1:	movl	%ecx, %edx
	call	__lll_mutex_lock_wait
	movl	%edx, %ecx
	jmp	2b

6:	movl	%ecx, %eax
	call	__lll_mutex_unlock_wake
	jmp	7b

10:	leal	MUTEX-READ_BLOCKERS(%ebx), %eax
	call	__lll_mutex_unlock_wake
	jmp	11b

12:	leal	MUTEX-READ_BLOCKERS(%ebx), %ecx
	call	__lll_mutex_lock_wait
	jmp	13b
	.size	__pthread_rwlock_rdlock,.-__pthread_rwlock_rdlock

	
	.globl	pthread_rwlock_rdlock
pthread_rwlock_rdlock = __pthread_rwlock_rdlock


	.globl	__pthread_rwlock_wrlock
	.type	__pthread_rwlock_wrlock,@function
	.align	16
__pthread_rwlock_wrlock:
	movl	4(%esp), %ecx

	/* Get the lock.  */
	movl	$1, %eax
	LOCK
	xaddl	%eax, MUTEX(%ecx)
	testl	%eax, %eax
	jne	1f

2:	movl	WRITE_BLOCKERS(%ecx), %edx
	testl	%edx, %edx
	jne	4f

	incl	READ_BLOCKERS(%ecx)
	
	/* writing is exclusive */
9:	incl	WRITE_BLOCKERS(%ecx)	
	incl	WRITERS(%ecx)

	/* drop lock */
	LOCK
	decl	MUTEX(%ecx)
	jne	6f
7:
	xorl	%eax, %eax
	ret


	
4:	pushl	%ebx
	pushl	%esi
	xorl	%esi, %esi

	/* maybe block readers */	
	movzbl	WRITE_PRE_ADD(%ecx), %eax
	addl	%eax, READ_BLOCKERS(%ecx)

1:	incl	WRITERS_QUEUED(%ecx)
	
	leal	WRITE_BLOCKERS(%ecx), %ebx
	
3:	/* drop lock */
	LOCK
	decl	MUTEX-WRITE_BLOCKERS(%ebx)
	jne	10f

11:	movl	%esi, %ecx	/* movl $FUTEX_WAIT, %ecx */
	movl	$SYS_futex, %eax
	int	$0x80

	/* Reget the lock.  */
	movl	$1, %eax
	LOCK
	xaddl	%eax, MUTEX-WRITE_BLOCKERS(%ebx)
	testl	%eax, %eax
	jne	12f

13:	movl	(%ebx), %edx
	testl	%edx, %edx
	jne	3b

	leal	-WRITE_BLOCKERS(%ebx), %ecx
	
	decl	WRITERS_QUEUED(%ecx)

	/* block readers if we didn't before */	
	movzbl	WRITE_POST_ADD(%ecx), %eax
	addl	%eax, READ_BLOCKERS(%ecx)
	
	popl	%esi
	popl	%ebx
	jmp	9b
	
	
1:	movl	%ecx, %edx
	call	__lll_mutex_lock_wait
	movl	%edx, %exx
	jmp	2b

6:	movl	%ecx, %eax
	call	__lll_mutex_unlock_wake
	jmp	7b

10:	leal	MUTEX-WRITE_BLOCKERS(%ebx), %eax
	call	__lll_mutex_unlock_wake
	jmp	11b

12:	leal	MUTEX-WRITE_BLOCKERS(%ebx), %ecx
	call	__lll_mutex_lock_wait
	jmp	13b
	.size	__pthread_rwlock_wrlock,.-__pthread_rwlock_wrlock

	.globl	pthread_rwlock_wrlock
pthread_rwlock_wrlock = __pthread_rwlock_wrlock


	.globl	__pthread_rwlock_unlock
	.type	__pthread_rwlock_unlock,@function
	.align	16
__pthread_rwlock_unlock:
	movl	4(%esp), %edx

	/* Get the lock.  */
	movl	$1, %eax
	LOCK
	xaddl	%eax, MUTEX(%edx)
	testl	%eax, %eax
	jne	1f

2:	cmpl	$0, WRITERS(%edx)
	jne	writer_unlock	

no_readers_check_writers:
	decl	WRITE_BLOCKERS(%edx)
	je	no_readers_check_writers_queued
	
6:
	LOCK
	decl	MUTEX(%edx)
	jne	3f

4:	xorl	%eax, %eax
	ret



writer_unlock:
	decl	WRITERS(%edx)
	/* recursive unlocks don't need to wake up anything */
	jne	6b	

check_writers:	
	decl	WRITE_BLOCKERS(%edx)
	je	check_writers_queued

no_writers_check_readers:	
	decl	READ_BLOCKERS(%edx)
	jne	6b

no_writers_check_readers_queued:
	cmpl	$0, READERS_QUEUED(%edx)
	je	6b
				
wake_readers:
	pushl	%ebx
	pushl	%esi
	xorl	%esi, %esi
	leal	READ_BLOCKERS(%ebx), %edx
	
	movl	$SYS_futex, %eax
	movl	$1, %ecx
	movl	$0x7fffffff, %edx
	int	$0x80
	
	leal	-READ_BLOCKERS(%ebx), %edx		
	popl	%esi
	popl	%ebx
	jmp	6b


	
check_writers_queued:
	cmpl	$0, WRITERS_QUEUED(%edx)
	je	no_writers_check_readers

wake_writers_check_readers:
	decl	READ_BLOCKERS(%edx)
	jne	wake_writers

wake_writers_check_readers_queued:	
	cmpl	$0, READERS_QUEUED(%edx)
	je	wake_writers

wake_both_choose:
	cmpw	$1, MODE(%edx)
	je	wake_readers
	jns	wake_writers

wake_both:
	pushl	%ebx	
	pushl	%esi
	xorl	%esi, %esi	
	leal	WRITE_BLOCKERS(%edx), %ebx
	
	movl	$SYS_futex, %eax
	movl	$1, %ecx
	movl	%ecx, %edx
	int	$0x80

	addl	$READ_BLOCKERS-WRITE_BLOCKERS, %ebx
	movl	$SYS_futex, %eax
	movl	$0x7fffffff, %ecx
	int	$0x80

	leal	-WRITE_BLOCKERS(%ebx), %edx	
	popl	%esi
	popl	%ebx	
	jmp	6b


	
no_readers_check_writers_queued:
	cmpl	$0, WRITERS_QUEUED(%edx)
	je	6b
	
wake_writers:
	pushl	%ebx	
	pushl	%esi
	xorl	%esi, %esi
	leal	WRITE_BLOCKERS(%edx), %ebx
	
	movl	$SYS_futex, %eax
	movl	$1, %ecx
	movl	%ecx, %edx
	int	$0x80

	leal	-WRITE_BLOCKERS(%ebx), %edx		
	popl	%esi
	popl	%ebx
	jmp	6b



1:	movl	%edx, %ecx
	call	__lll_mutex_lock_wait
	jmp	2b

3:	movl	%edx, %eax
	call	__lll_mutex_unlock_wake
	jmp	4b

	.size	__pthread_rwlock_unlock,.-__pthread_rwlock_unlock

	.globl	pthread_rwlock_unlock
pthread_rwlock_unlock = __pthread_rwlock_unlock

Attachment: signature.asc
Description: This is a digitally signed message part


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