userspace spinlocks

userspace spinlocks

[Florian Lohoff]

Hi,
while compiling db2 i got the configure warning "spinlocks not implemented
for this compiler/architecture" - I guess as we do not currently have
SMP machines (except the ones ralf is working on) we dont have a problem,
but how should the spinlocks be implemented ?

I mean - normally "ll" and "sc" are needed - But those are not
available on R3000 - And spinning in an ll/sc loop and emulating
them with exceptions isnt that fast.

OTOH - Where are they normally implemented ? libc ? macro ? Could
there be a runtime linking thing with a cpu detection wether we 
have ll/sc or not ?

Flo
-- 
Florian Lohoff                  flo@rfc822.org             +49-5201-669912
     Why is it called "common sense" when nobody seems to have any?

Re: userspace spinlocks

[Jun Sun]

Florian Lohoff wrote:
> 
> OTOH - Where are they normally implemented ? libc ? macro ? 

As far I know, they ether use atomic instructions such as ll/sc or use
kernel trap to emulate atomic operations.  I am not sure if other means
are possible because userland cannot disable interrupts or prevent
context switch.

> Could
> there be a runtime linking thing with a cpu detection wether we
> have ll/sc or not ?
>

This is a wonderful idea.  It should incorporate into future MIPS CPU
support structure.
 
Jun

Re: userspace spinlocks

[Ralf Baechle]

On Mon, Oct 30, 2000 at 09:51:06AM -0800, Jun Sun wrote:

> > Could
> > there be a runtime linking thing with a cpu detection wether we
> > have ll/sc or not ?
> 
> This is a wonderful idea.  It should incorporate into future MIPS CPU
> support structure.

But what is the better alternative?  Emulating ll/sc is a generic facility.
Aside of making that more efficient the only idea I have is putting entire
atomic operations into the kernel such that the standard case should result
in at most one exception to be handled in the kernel.

Btw, could somebody put a counter into the ll/sc emulator and test how
often it gets called on a R3000 machine?

  Ralf

Re: userspace spinlocks

[Jun Sun]

Ralf Baechle wrote:
> 
> On Mon, Oct 30, 2000 at 09:51:06AM -0800, Jun Sun wrote:
> 
> > > Could
> > > there be a runtime linking thing with a cpu detection wether we
> > > have ll/sc or not ?
> >
> > This is a wonderful idea.  It should incorporate into future MIPS CPU
> > support structure.
> 
> But what is the better alternative?  Emulating ll/sc is a generic facility.
> Aside of making that more efficient the only idea I have is putting entire
> atomic operations into the kernel such that the standard case should result
> in at most one exception to be handled in the kernel.
> 

When I was playing with NEC Vr4111 (a MIPS III cpu but without ll/sc), I
notice the following comment in
glibc/linuxthreads/sysdeps/mips/pt-machine.h file (Is that Ralf's
comment?) :

"
   TODO: This version makes use of MIPS ISA 2 features.  It won't
   work on ISA 1.  These machines will have to take the overhead of
   a sysmips(MIPS_ATOMIC_SET, ...) syscall which isn't implemented
   yet correctly.  There is however a better solution for R3000
   uniprocessor machines possible.  */
"

I remembered I found a patch which actually uses mips syscalls.  For
some reasons, it did not work in the end.

BTW, I didn't know the kernel already has ll/sc emulation.  That seems
to be necessary, even just for the binary compability sake.

Jun

RE: userspace spinlocks

[Mike Klar]

Jun Sun wrote:

> BTW, I didn't know the kernel already has ll/sc emulation.  That seems
> to be necessary, even just for the binary compability sake.

It's not complete in the Linux-MIPS tree, it is at least more so in the
Linux VR tree, but still only supports locking between user contexts.  Patch
is below, sorry if it doesn't apply cleanly, there were a few bits that I
cut out that weren't pertinent to LL/SC.

The bits that have to do with ll_task in the below patch look wrong, though,
and I only just noticed when preparing this patch that it had gotten added.
I'm not sure what the motivation for adding it was, maybe clearing ll_bit
only on context switches was not sufficient to cover all cases (like thread
creation, maybe?), but I thought I had looked into that already.

Mike Klar

Index: arch/mips/kernel/traps.c
===================================================================
RCS file: /cvsroot/linux-vr/linux/arch/mips/kernel/traps.c,v
retrieving revision 1.1.1.7
retrieving revision 1.20
diff -u -d -r1.1.1.7 -r1.20
--- arch/mips/kernel/traps.c	2000/09/12 06:41:24	1.1.1.7
+++ arch/mips/kernel/traps.c	2000/09/13 07:24:52	1.20
@@ -95,9 +95,9 @@
 #define RT     0x001f0000
 #define OFFSET 0x0000ffff
 #define LL     0xc0000000
-#define SC     0xd0000000
+#define SC     0xe0000000

-#define DEBUG_LLSC
+#undef DEBUG_LLSC
 #endif

 /*
@@ -418,47 +423,65 @@
 #if !defined(CONFIG_CPU_HAS_LLSC)

 /*
- * userland emulation for R2300 CPUs
+ * userland emulation for R2300 CPUs, and some embedded R4K CPUs
  * needed for the multithreading part of glibc
+ *
+ * this implementation can handle only sychronization between 2 or more
+ * user contexts.
  */
 void do_ri(struct pt_regs *regs)
 {
 	unsigned int opcode;

+	if (!user_mode(regs))
+		BUG();
+
 	if (!get_insn_opcode(regs, &opcode)) {
-		if ((opcode & OPCODE) == LL)
+		if ((opcode & OPCODE) == LL) {
 			simulate_ll(regs, opcode);
-		if ((opcode & OPCODE) == SC)
+			return;
+		}
+		if ((opcode & OPCODE) == SC) {
 			simulate_sc(regs, opcode);
-	} else {
-	printk("[%s:%d] Illegal instruction at %08lx ra=%08lx\n",
-	       current->comm, current->pid, regs->cp0_epc, regs->regs[31]);
+			return;
+		}
 	}
+	printk("[%s:%d] Illegal instruction %08lx at %08lx, ra=%08lx,
CP0_STATUS=%08lx\n",
+	       current->comm, current->pid, *((unsigned long*)regs->cp0_epc),
regs->cp0_epc,
+		regs->regs[31], regs->cp0_status);
 	if (compute_return_epc(regs))
 		return;
 	force_sig(SIGILL, current);
 }

 /*
- * the ll_bit will be cleared by r2300_switch.S
+ * the ll_bit will be cleared by r2300_switch.S or r4k_switch.S
  */
-unsigned long ll_bit, *lladdr;
+unsigned long ll_bit;
+#ifdef CONFIG_SMP
+unsigned long *lladdr;
+#endif
+
+static struct task_struct *ll_task = NULL;

 void simulate_ll(struct pt_regs *regp, unsigned int opcode)
 {
-	unsigned long *addr, *vaddr;
+	unsigned long value, *vaddr;
 	long offset;
+	int signal = 0;
+#ifdef CONFIG_SMP
+	unsigned long *addr;
+#endif

 	/*
 	 * analyse the ll instruction that just caused a ri exception
 	 * and put the referenced address to addr.
 	 */
+
 	/* sign extend offset */
 	offset = opcode & OFFSET;
-	if (offset & 0x00008000)
-		offset = -(offset & 0x00007fff);
-	else
-		offset = (offset & 0x00007fff);
+	offset <<= 16;
+	offset >>= 16;

 	vaddr = (unsigned long *)((long)(regp->regs[(opcode & BASE) >> 21]) +
offset);

@@ -466,31 +489,51 @@
 	printk("ll: vaddr = 0x%08x, reg = %d\n", (unsigned int)vaddr, (opcode &
RT) >> 16);
 #endif

+#ifdef CONFIG_SMP
 	/*
 	 * TODO: compute physical address from vaddr
 	 */
-	panic("ll: emulation not yet finished!");
+	panic("ll: emulation not yet finished for SMP!");

 	lladdr = addr;
-	ll_bit = 1;
-	regp->regs[(opcode & RT) >> 16] = *addr;
+#endif
+	if ((unsigned long)vaddr & 3)
+		signal = SIGBUS;
+	else if (get_user(value, vaddr))
+		signal = SIGSEGV;
+	else {
+		if (ll_task == NULL || ll_task == current) {
+			ll_bit = 1;
+		} else {
+			ll_bit = 0;
+		}
+		ll_task = current;
+		regp->regs[(opcode & RT) >> 16] = value;
+	}
+	if (compute_return_epc(regp))
+		return;
+	if (signal)
+		send_sig(signal, current, 1);
 }

 void simulate_sc(struct pt_regs *regp, unsigned int opcode)
 {
-	unsigned long *addr, *vaddr, reg;
+	unsigned long *vaddr, reg;
 	long offset;
+	int signal = 0;
+#ifdef CONFIG_SMP
+	unsigned long *addr;
+#endif

 	/*
 	 * analyse the sc instruction that just caused a ri exception
 	 * and put the referenced address to addr.
 	 */
+
 	/* sign extend offset */
 	offset = opcode & OFFSET;
-	if (offset & 0x00008000)
-		offset = -(offset & 0x00007fff);
-	else
-		offset = (offset & 0x00007fff);
+	offset <<= 16;
+	offset >>= 16;

 	vaddr = (unsigned long *)((long)(regp->regs[(opcode & BASE) >> 21]) +
offset);
 	reg = (opcode & RT) >> 16;
@@ -499,20 +542,26 @@
 	printk("sc: vaddr = 0x%08x, reg = %d\n", (unsigned int)vaddr, (unsigned
int)reg);
 #endif

+#ifdef CONFIG_SMP
 	/*
 	 * TODO: compute physical address from vaddr
 	 */
-	panic("sc: emulation not yet finished!");
+	panic("sc: emulation not yet finished for SMP!");

 	lladdr = addr;
-
-	if (ll_bit == 0) {
+#endif
+	if ((unsigned long)vaddr & 3)
+		signal = SIGBUS;
+	else if (ll_bit == 0 || ll_task != current)
 		regp->regs[reg] = 0;
+	else if (put_user(regp->regs[reg], vaddr))
+		signal = SIGSEGV;
+	else
+		regp->regs[reg] = 1;
+	if (compute_return_epc(regp))
 		return;
-	}
-
-	*addr = regp->regs[reg];
-	regp->regs[reg] = 1;
+	if (signal)
+		send_sig(signal, current, 1);
 }

 #else /* MIPS 2 or higher */
Index: arch/mips/kernel/r2300_switch.S
===================================================================
RCS file: /cvsroot/linux-vr/linux/arch/mips/kernel/r2300_switch.S,v
retrieving revision 1.1.1.2
retrieving revision 1.2
diff -u -d -r1.1.1.2 -r1.2
--- arch/mips/kernel/r2300_switch.S	2000/04/12 02:42:46	1.1.1.2
+++ arch/mips/kernel/r2300_switch.S	2000/07/19 07:18:06	1.2
@@ -34,6 +34,7 @@
  *                           task_struct *next)
  */
 LEAF(resume)
+	sw	zero, ll_bit
 	.set	reorder
 	mfc0	t1, CP0_STATUS
 	.set	noreorder
Index: arch/mips/kernel/r4k_switch.S
===================================================================
RCS file: /cvsroot/linux-vr/linux/arch/mips/kernel/r4k_switch.S,v
retrieving revision 1.1.1.2
retrieving revision 1.2
diff -u -d -r1.1.1.2 -r1.2
--- arch/mips/kernel/r4k_switch.S	2000/04/12 02:42:47	1.1.1.2
+++ arch/mips/kernel/r4k_switch.S	2000/07/19 07:18:06	1.2
@@ -9,6 +9,7 @@
  * Copyright (C) 1994, 1995, 1996, by Andreas Busse
  * Copyright (C) 1999 Silicon Graphics, Inc.
  */
+#include <linux/config.h>
 #include <asm/asm.h>
 #include <asm/bootinfo.h>
 #include <asm/cachectl.h>
@@ -32,6 +33,9 @@
 	.set	noreorder
 	.align	5
 	LEAF(resume)
+#ifndef CONFIG_CPU_HAS_LLSC
+	sw	zero, ll_bit
+#endif
 	mfc0	t1, CP0_STATUS
 	sw	t1, THREAD_STATUS(a0)
 	CPU_SAVE_NONSCRATCH(a0)

RE: userspace spinlocks

[Mike Klar]

Jun Sun wrote:

> BTW, I didn't know the kernel already has ll/sc emulation.  That seems
> to be necessary, even just for the binary compability sake.

It's not complete in the Linux-MIPS tree, it is at least more so in the
Linux VR tree, but still only supports locking between user contexts.  Patch
is below, sorry if it doesn't apply cleanly, there were a few bits that I
cut out that weren't pertinent to LL/SC.

The bits that have to do with ll_task in the below patch look wrong, though,
and I only just noticed when preparing this patch that it had gotten added.
I'm not sure what the motivation for adding it was, maybe clearing ll_bit
only on context switches was not sufficient to cover all cases (like thread
creation, maybe?), but I thought I had looked into that already.

Mike Klar

Index: arch/mips/kernel/traps.c
===================================================================
RCS file: /cvsroot/linux-vr/linux/arch/mips/kernel/traps.c,v
retrieving revision 1.1.1.7
retrieving revision 1.20
diff -u -d -r1.1.1.7 -r1.20
--- arch/mips/kernel/traps.c	2000/09/12 06:41:24	1.1.1.7
+++ arch/mips/kernel/traps.c	2000/09/13 07:24:52	1.20
@@ -95,9 +95,9 @@
 #define RT     0x001f0000
 #define OFFSET 0x0000ffff
 #define LL     0xc0000000
-#define SC     0xd0000000
+#define SC     0xe0000000

-#define DEBUG_LLSC
+#undef DEBUG_LLSC
 #endif

 /*
@@ -418,47 +423,65 @@
 #if !defined(CONFIG_CPU_HAS_LLSC)

 /*
- * userland emulation for R2300 CPUs
+ * userland emulation for R2300 CPUs, and some embedded R4K CPUs
  * needed for the multithreading part of glibc
+ *
+ * this implementation can handle only sychronization between 2 or more
+ * user contexts.
  */
 void do_ri(struct pt_regs *regs)
 {
 	unsigned int opcode;

+	if (!user_mode(regs))
+		BUG();
+
 	if (!get_insn_opcode(regs, &opcode)) {
-		if ((opcode & OPCODE) == LL)
+		if ((opcode & OPCODE) == LL) {
 			simulate_ll(regs, opcode);
-		if ((opcode & OPCODE) == SC)
+			return;
+		}
+		if ((opcode & OPCODE) == SC) {
 			simulate_sc(regs, opcode);
-	} else {
-	printk("[%s:%d] Illegal instruction at %08lx ra=%08lx\n",
-	       current->comm, current->pid, regs->cp0_epc, regs->regs[31]);
+			return;
+		}
 	}
+	printk("[%s:%d] Illegal instruction %08lx at %08lx, ra=%08lx,
CP0_STATUS=%08lx\n",
+	       current->comm, current->pid, *((unsigned long*)regs->cp0_epc),
regs->cp0_epc,
+		regs->regs[31], regs->cp0_status);
 	if (compute_return_epc(regs))
 		return;
 	force_sig(SIGILL, current);
 }

 /*
- * the ll_bit will be cleared by r2300_switch.S
+ * the ll_bit will be cleared by r2300_switch.S or r4k_switch.S
  */
-unsigned long ll_bit, *lladdr;
+unsigned long ll_bit;
+#ifdef CONFIG_SMP
+unsigned long *lladdr;
+#endif
+
+static struct task_struct *ll_task = NULL;

 void simulate_ll(struct pt_regs *regp, unsigned int opcode)
 {
-	unsigned long *addr, *vaddr;
+	unsigned long value, *vaddr;
 	long offset;
+	int signal = 0;
+#ifdef CONFIG_SMP
+	unsigned long *addr;
+#endif

 	/*
 	 * analyse the ll instruction that just caused a ri exception
 	 * and put the referenced address to addr.
 	 */
+
 	/* sign extend offset */
 	offset = opcode & OFFSET;
-	if (offset & 0x00008000)
-		offset = -(offset & 0x00007fff);
-	else
-		offset = (offset & 0x00007fff);
+	offset <<= 16;
+	offset >>= 16;

 	vaddr = (unsigned long *)((long)(regp->regs[(opcode & BASE) >> 21]) +
offset);

@@ -466,31 +489,51 @@
 	printk("ll: vaddr = 0x%08x, reg = %d\n", (unsigned int)vaddr, (opcode &
RT) >> 16);
 #endif

+#ifdef CONFIG_SMP
 	/*
 	 * TODO: compute physical address from vaddr
 	 */
-	panic("ll: emulation not yet finished!");
+	panic("ll: emulation not yet finished for SMP!");

 	lladdr = addr;
-	ll_bit = 1;
-	regp->regs[(opcode & RT) >> 16] = *addr;
+#endif
+	if ((unsigned long)vaddr & 3)
+		signal = SIGBUS;
+	else if (get_user(value, vaddr))
+		signal = SIGSEGV;
+	else {
+		if (ll_task == NULL || ll_task == current) {
+			ll_bit = 1;
+		} else {
+			ll_bit = 0;
+		}
+		ll_task = current;
+		regp->regs[(opcode & RT) >> 16] = value;
+	}
+	if (compute_return_epc(regp))
+		return;
+	if (signal)
+		send_sig(signal, current, 1);
 }

 void simulate_sc(struct pt_regs *regp, unsigned int opcode)
 {
-	unsigned long *addr, *vaddr, reg;
+	unsigned long *vaddr, reg;
 	long offset;
+	int signal = 0;
+#ifdef CONFIG_SMP
+	unsigned long *addr;
+#endif

 	/*
 	 * analyse the sc instruction that just caused a ri exception
 	 * and put the referenced address to addr.
 	 */
+
 	/* sign extend offset */
 	offset = opcode & OFFSET;
-	if (offset & 0x00008000)
-		offset = -(offset & 0x00007fff);
-	else
-		offset = (offset & 0x00007fff);
+	offset <<= 16;
+	offset >>= 16;

 	vaddr = (unsigned long *)((long)(regp->regs[(opcode & BASE) >> 21]) +
offset);
 	reg = (opcode & RT) >> 16;
@@ -499,20 +542,26 @@
 	printk("sc: vaddr = 0x%08x, reg = %d\n", (unsigned int)vaddr, (unsigned
int)reg);
 #endif

+#ifdef CONFIG_SMP
 	/*
 	 * TODO: compute physical address from vaddr
 	 */
-	panic("sc: emulation not yet finished!");
+	panic("sc: emulation not yet finished for SMP!");

 	lladdr = addr;
-
-	if (ll_bit == 0) {
+#endif
+	if ((unsigned long)vaddr & 3)
+		signal = SIGBUS;
+	else if (ll_bit == 0 || ll_task != current)
 		regp->regs[reg] = 0;
+	else if (put_user(regp->regs[reg], vaddr))
+		signal = SIGSEGV;
+	else
+		regp->regs[reg] = 1;
+	if (compute_return_epc(regp))
 		return;
-	}
-
-	*addr = regp->regs[reg];
-	regp->regs[reg] = 1;
+	if (signal)
+		send_sig(signal, current, 1);
 }

 #else /* MIPS 2 or higher */
Index: arch/mips/kernel/r2300_switch.S
===================================================================
RCS file: /cvsroot/linux-vr/linux/arch/mips/kernel/r2300_switch.S,v
retrieving revision 1.1.1.2
retrieving revision 1.2
diff -u -d -r1.1.1.2 -r1.2
--- arch/mips/kernel/r2300_switch.S	2000/04/12 02:42:46	1.1.1.2
+++ arch/mips/kernel/r2300_switch.S	2000/07/19 07:18:06	1.2
@@ -34,6 +34,7 @@
  *                           task_struct *next)
  */
 LEAF(resume)
+	sw	zero, ll_bit
 	.set	reorder
 	mfc0	t1, CP0_STATUS
 	.set	noreorder
Index: arch/mips/kernel/r4k_switch.S
===================================================================
RCS file: /cvsroot/linux-vr/linux/arch/mips/kernel/r4k_switch.S,v
retrieving revision 1.1.1.2
retrieving revision 1.2
diff -u -d -r1.1.1.2 -r1.2
--- arch/mips/kernel/r4k_switch.S	2000/04/12 02:42:47	1.1.1.2
+++ arch/mips/kernel/r4k_switch.S	2000/07/19 07:18:06	1.2
@@ -9,6 +9,7 @@
  * Copyright (C) 1994, 1995, 1996, by Andreas Busse
  * Copyright (C) 1999 Silicon Graphics, Inc.
  */
+#include <linux/config.h>
 #include <asm/asm.h>
 #include <asm/bootinfo.h>
 #include <asm/cachectl.h>
@@ -32,6 +33,9 @@
 	.set	noreorder
 	.align	5
 	LEAF(resume)
+#ifndef CONFIG_CPU_HAS_LLSC
+	sw	zero, ll_bit
+#endif
 	mfc0	t1, CP0_STATUS
 	sw	t1, THREAD_STATUS(a0)
 	CPU_SAVE_NONSCRATCH(a0)

Re: userspace spinlocks

[Ralf Baechle]

On Tue, Oct 31, 2000 at 10:50:39PM -0800, Mike Klar wrote:

> > BTW, I didn't know the kernel already has ll/sc emulation.  That seems
> > to be necessary, even just for the binary compability sake.
> 
> It's not complete in the Linux-MIPS tree, it is at least more so in the
> Linux VR tree, but still only supports locking between user contexts.  Patch
> is below, sorry if it doesn't apply cleanly, there were a few bits that I
> cut out that weren't pertinent to LL/SC.
> 
> The bits that have to do with ll_task in the below patch look wrong, though,
> and I only just noticed when preparing this patch that it had gotten added.
> I'm not sure what the motivation for adding it was, maybe clearing ll_bit
> only on context switches was not sufficient to cover all cases (like thread
> creation, maybe?), but I thought I had looked into that already.

Ok, I'll take this and try to hack it into shape.  I especially don't
like putting anything into the scheduler - another 5 ns for a 200MHz box
per cotext switch go down the drain.  For sanity reasons I also think we
don't want to support SMP for the ll/sc emulation.

  Ralf

RE: userspace spinlocks

[Mike Klar]

Ralf Baechle wrote:

> Ok, I'll take this and try to hack it into shape.  I especially don't
> like putting anything into the scheduler - another 5 ns for a 200MHz box
> per cotext switch go down the drain.

I agree that's pretty nasty, but I don't see any other way to break the link
on context switches that doesn't also add the same overhead (if not more).
The worst part of it is the extra store per context switch happens even if
you don't ever use ll/sc.

You could probably implement locking primitives without it, but then you're
getting away from actually emulating ll and sc.  I guess that's not a big
deal, since we're already not emulating them 100%, but the further you get
from the actual functionality of the instructions, the more likely it is to
break some user space code when someone decides to be "clever" with ll/sc by
using them per the hardware ll/sc specification.

Then again, I'm just ranting here, since the clear-it-in-the-resume-function
approach apparently wasn't doing what it should have 100% anyway.

> For sanity reasons I also think we
> don't want to support SMP for the ll/sc emulation.

I agree.  It's not impossible to do, but very much non-trivial, for
something that will probably never be used anyway.  The embedded R4K CPUs
that I've seen without ll/sc give lack of SMP support as the reason for not
implementing ll/sc.  Sigh... as if uniprocessor systems never need locking
primitives....

Mike K.

RE: userspace spinlocks

[Mike Klar]

Ralf Baechle wrote:

> Ok, I'll take this and try to hack it into shape.  I especially don't
> like putting anything into the scheduler - another 5 ns for a 200MHz box
> per cotext switch go down the drain.

I agree that's pretty nasty, but I don't see any other way to break the link
on context switches that doesn't also add the same overhead (if not more).
The worst part of it is the extra store per context switch happens even if
you don't ever use ll/sc.

You could probably implement locking primitives without it, but then you're
getting away from actually emulating ll and sc.  I guess that's not a big
deal, since we're already not emulating them 100%, but the further you get
from the actual functionality of the instructions, the more likely it is to
break some user space code when someone decides to be "clever" with ll/sc by
using them per the hardware ll/sc specification.

Then again, I'm just ranting here, since the clear-it-in-the-resume-function
approach apparently wasn't doing what it should have 100% anyway.

> For sanity reasons I also think we
> don't want to support SMP for the ll/sc emulation.

I agree.  It's not impossible to do, but very much non-trivial, for
something that will probably never be used anyway.  The embedded R4K CPUs
that I've seen without ll/sc give lack of SMP support as the reason for not
implementing ll/sc.  Sigh... as if uniprocessor systems never need locking
primitives....

Mike K.

Re: userspace spinlocks

[Florian Lohoff]

On Tue, Oct 31, 2000 at 09:14:31PM +0100, Ralf Baechle wrote:
> But what is the better alternative?  Emulating ll/sc is a generic facility.
> Aside of making that more efficient the only idea I have is putting entire
> atomic operations into the kernel such that the standard case should result
> in at most one exception to be handled in the kernel.

Its just that i fell over db-2.7.7 which told me on configure that
it cant find "spinlocks" for this architecture - I had a closer look
now and it seems they have asm files for each cpu type on how to 
implement the atomic "test and set" logic. But nothing for mips.
There is a long README stating that there is no real portable way
on how to do locking and if no architecture atomic "test and set" logic
would be available they would use some complicated fnctl semantics.

> Btw, could somebody put a counter into the ll/sc emulator and test how
> often it gets called on a R3000 machine?

I hope never Sir

arch/mips/kernel/traps.c

    466         /*
    467          * TODO: compute physical address from vaddr
    468          */
    469         panic("ll: emulation not yet finished!");
    470

Flo
-- 
Florian Lohoff                  flo@rfc822.org             +49-5201-669912
     Why is it called "common sense" when nobody seems to have any?

Re: userspace spinlocks

[Ralf Baechle]

On Mon, Oct 30, 2000 at 03:17:36PM +0100, Florian Lohoff wrote:

> Hi,
> while compiling db2 i got the configure warning "spinlocks not implemented
> for this compiler/architecture" - I guess as we do not currently have
> SMP machines (except the ones ralf is working on) we dont have a problem,
> but how should the spinlocks be implemented ?

Think multithreadeding.  We do have the problem on every machine.

> I mean - normally "ll" and "sc" are needed - But those are not
> available on R3000 - And spinning in an ll/sc loop and emulating
> them with exceptions isnt that fast.

The assumption is that spinlocks have low contention so we don't loop.

Face it - the R3000 is completly idiotic processor to use in multiprocessor
systems.  Early R3000 SMP systems as built by SGI in the 80's did use
special external hardware to implement atomic operations.  Any atomic
operation was very expensive.  An old way to implement threadsafe atomic
operations is the sysmips(MIPS_ATOMIC_SET) interface, essentially a
syscall that implements atomic set-and-exchange functionality.  Something
that only continues to live as a compatibility relict.

We don't support R3000 SMP but multithreading turns out to be a similar
problem.  Computer science offers a number of algorithems which only
require atomic stores.  Their common problem is that they're aproximately
O(n^2) in the average or O(n) and have memory requirements proprortional
to n.  All in all it comes down to the fact that they're frighteningly
useless for realworld use.

For all this reasons I've choosen to simply implement userspace locking
by simply emulating ll/sc where not available.

If somebody really thinks the performance of this operations is a problem
well, our implementation is hardly optimal.

> OTOH - Where are they normally implemented ? libc ? macro ? Could
> there be a runtime linking thing with a cpu detection wether we 
> have ll/sc or not ?

Typical databases carry their own locking routines which are very well
tuned toward the behaviour of the database.

  Ralf