read/write semaphores

PATCH New Andrew Morton 1 participant 1 message Apr 9, 2001

Subsystems (2)

Library code Scheduler

lore

Share & tools

lore

Andrew Morton

author

2001-04-09 00:16 UTC #0 lore raw

PATCH 1/1 read/write semaphores

This is a new implementation. After ~20 hours effort I couldn't get the current x86 rwsem code to work.

This patch breaks all architechtures, but it's a good break and trivial to fix. It removes the `RW_LOCK_BIAS' arg in include/linux/sched.h:INIT_MM().

This code is architecture-independent. It is intended (by me) that all architectures dump their existing rwsem implementation and use this one. It creates include/linux/rw_semaphore.h and lib/rw_semaphore.c. If other architectures are to use this implementation of rwsems then the following must be done:

1: delete the existing rwsem code
2: in include/asm/semaphore.h, add:

	#define ARCH_USES_GENERIC_RWSEM
	#include <linux/rw_semaphore.h>

It would be better to split rw_semaphore.h away from semaphore.h altogether, but that's a lot of mangling.

There are several ways of designing rwsems. This patch takes a simple approach:

- If a writer wants the lock and it's free, grant.
- If a reader wants the lock and it's not held by a writer and there are no writers waiting for it, grant.
- when the lock is being released, and there are both readers and writers waiting on it, we grant it to writers.

So writers-starved-by-readers cannot occur. This is because new readers block when they see a writer is requesting the rwsem.

Writers *can* starve readers. If a task is hammering away on down_write()/up_write() then readers never manage to get a hold of the semaphore. Hopefully this won't be a problem. It's fixable by introducing more state into the rwsem.

It is not legal to do an up_read() or up_write() from interrupt context. See the comments in rw_semaphore.c

It is not legal for one task to do more than one concurrent down_read() on an rwsem. You can't do:

	down_read(sem);
	...
	down_read(sem);

because an intervening down_write() by another task will cause deadlock. See comments in rw_semaphore.c

Patches against 2.4.3-ac2 and 2.4.3 are attached.

There's some rwsem testing code at

http://www.uow.edu.au/~andrewm/linux/rwsem.tar.gz

which may be used to verify this patch. rwsem-4.c is the most useful.

include/linux/sched.h +1 -1

@@ -241,7 +241,7 @@
 	mm_users:	ATOMIC_INIT(2), 		\
 	mm_count:	ATOMIC_INIT(1), 		\
 	map_count:	1, 				\
-	mmap_sem:	__RWSEM_INITIALIZER(name.mmap_sem, RW_LOCK_BIAS), \
+	mmap_sem:	__RWSEM_INITIALIZER(name.mmap_sem), \
 	page_table_lock: SPIN_LOCK_UNLOCKED, 		\
 	mmlist:		LIST_HEAD_INIT(name.mmlist),	\
 }

include/linux/rw_semaphore.h +136 -0

136 lines not on this page · raw message

arch/i386/kernel/semaphore.c +22 ~~-193~~

233 lines not on this page · raw message

include/asm-i386/semaphore.h +6 ~~-180~~

195 lines not on this page · raw message

arch/i386/kernel/i386_ksyms.c +0 ~~-14~~

@@ -38,11 +38,6 @@
 EXPORT_SYMBOL(machine_real_restart);
 #endif
 
-#ifdef CONFIG_SMP
-extern void FASTCALL( __write_lock_failed(rwlock_t *rw));
-extern void FASTCALL( __read_lock_failed(rwlock_t *rw));
-#endif
-
 #if defined(CONFIG_BLK_DEV_IDE) || defined(CONFIG_BLK_DEV_HD) || defined(CONFIG_BLK_DEV_IDE_MODULE) || defined(CONFIG_BLK_DEV_HD_MODULE)
 extern struct drive_info_struct drive_info;
 EXPORT_SYMBOL(drive_info);

@@ -76,13 +71,6 @@
 EXPORT_SYMBOL(apm_info);
 EXPORT_SYMBOL(gdt);
 
-EXPORT_SYMBOL_NOVERS(__down_failed);
-EXPORT_SYMBOL_NOVERS(__down_failed_interruptible);
-EXPORT_SYMBOL_NOVERS(__down_failed_trylock);
-EXPORT_SYMBOL_NOVERS(__up_wakeup);
-EXPORT_SYMBOL_NOVERS(__down_write_failed);
-EXPORT_SYMBOL_NOVERS(__down_read_failed);
-EXPORT_SYMBOL_NOVERS(__rwsem_wake);
 /* Networking helper routines. */
 EXPORT_SYMBOL(csum_partial_copy_generic);
 /* Delay loops */

@@ -128,8 +116,6 @@
 EXPORT_SYMBOL(kernel_flag);
 EXPORT_SYMBOL(smp_num_cpus);
 EXPORT_SYMBOL(cpu_online_map);
-EXPORT_SYMBOL_NOVERS(__write_lock_failed);
-EXPORT_SYMBOL_NOVERS(__read_lock_failed);
 
 /* Global SMP irq stuff */
 EXPORT_SYMBOL(synchronize_irq);

arch/i386/kernel/Makefile +1 -1

@@ -14,7 +14,7 @@
 
 O_TARGET := kernel.o
 
-export-objs     := mca.o mtrr.o msr.o cpuid.o microcode.o i386_ksyms.o
+export-objs     := mca.o mtrr.o msr.o cpuid.o microcode.o i386_ksyms.o semaphore.o
 
 obj-y	:= process.o semaphore.o signal.o entry.o traps.o irq.o vm86.o \
 		ptrace.o i8259.o ioport.o ldt.o setup.o time.o sys_i386.o \

lib/rw_semaphore.c +135 -0

135 lines not on this page · raw message

lib/Makefile +4 -2

@@ -8,9 +8,11 @@
 
 L_TARGET := lib.a
 
-export-objs := cmdline.o
+export-objs := cmdline.o rw_semaphore.o
 
-obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o bust_spinlocks.o
+obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o \
+	bust_spinlocks.o rw_semaphore.o
+	
 
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y) 
   obj-y += dec_and_lock.o