Who owns those locks ?

Who owns those locks ?

[Zoltan Menyhart]

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

Got a dead lock ?
No idea how you got there ?

Why don't you put the ID of the owner of the lock in the lock word ?
Here is your patch for IA-64.
Doesn't cost any additional instruction, you can have it in your
"production" kernel, too.

The current task pointers are identity mapped memory addresses.
I shift them to the right by 12 bits (these bits are always 0-s).
In that way, addresses up to 16 Tbytes can fit into the lock word.

Interrupt handlers use the current task pointers as IDs, too.
An interrupt handler has to free all the locks it has taken,
therefore using the same ID as the task pre-empted uses, is not
confusing. Locks which are taken with / without interrupt disabling
form two distinct sets.
If you are back into the pre-empted task and should there is a
"left over" lock with the ID of the task => you've got a hint ;-)

In debug mode, you can check if the lock is yours before setting it free:

#define spin_is_mine(x)	((x)->lock == (__u32)((__u64) current >> 12))

Good luck.


Zoltán Menyhárt

[-- Attachment #2: n475 --]
[-- Type: text/plain, Size: 2553 bytes --]

--- 2.6.5.ref/include/asm-ia64/spinlock.h	Sun Apr  4 05:36:17 2004
+++ 2.6.5.new/include/asm-ia64/spinlock.h	Wed May 12 10:29:38 2004
@@ -45,7 +45,8 @@
 	asm volatile ("{\n\t"
 		      "  mov ar.ccv = r0\n\t"
 		      "  mov r28 = ip\n\t"
-		      "  mov r30 = 1;;\n\t"
+		      /* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "}\n\t"
 		      "cmpxchg4.acq r30 = [%1], r30, ar.ccv\n\t"
 		      "movl r29 = ia64_spinlock_contention_pre3_4;;\n\t"
@@ -57,7 +58,8 @@
 	asm volatile ("{\n\t"
 		      "  mov ar.ccv = r0\n\t"
 		      "  mov r28 = ip\n\t"
-		      "  mov r30 = 1;;\n\t"
+		      /* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "}\n\t"
 		      "cmpxchg4.acq r30 = [%1], r30, ar.ccv;;\n\t"
 		      "cmp4.ne p14, p0 = r30, r0\n"
@@ -68,7 +70,8 @@
 # ifdef CONFIG_ITANIUM
 	/* don't use brl on Itanium... */
 	/* mis-declare, so we get the entry-point, not it's function descriptor: */
-	asm volatile ("mov r30 = 1\n\t"
+	asm volatile (/* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "mov ar.ccv = r0;;\n\t"
 		      "cmpxchg4.acq r30 = [%0], r30, ar.ccv\n\t"
 		      "movl r29 = ia64_spinlock_contention;;\n\t"
@@ -77,7 +80,8 @@
 		      "(p14) br.call.spnt.many b6 = b6"
 		      : "=r"(ptr) : "r"(ptr) : IA64_SPINLOCK_CLOBBERS);
 # else
-	asm volatile ("mov r30 = 1\n\t"
+	asm volatile (/* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "mov ar.ccv = r0;;\n\t"
 		      "cmpxchg4.acq r30 = [%0], r30, ar.ccv;;\n\t"
 		      "cmp4.ne p14, p0 = r30, r0\n\t"
@@ -89,14 +93,17 @@
 #else /* !ASM_SUPPORTED */
 # define _raw_spin_lock(x)								\
 do {											\
-	__u32 *ia64_spinlock_ptr = (__u32 *) (x);					\
-	__u64 ia64_spinlock_val;							\
-	ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr, 1, 0);			\
+	__u32	*ia64_spinlock_ptr = (__u32 *) (x);					\
+	__u64	ia64_spinlock_val;							\
+	__u32	new_spinlock_val = (__u32)((__u64) current >> 12);			\
+											\
+	ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr, new_spinlock_val, 0);	\
 	if (unlikely(ia64_spinlock_val)) {						\
 		do {									\
 			while (*ia64_spinlock_ptr)					\
 				ia64_barrier();						\
-			ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr, 1, 0);	\
+			ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr,	\
+								new_spinlock_val, 0);	\
 		} while (ia64_spinlock_val);						\
 	}										\
 } while (0)

RE: Who owns those locks ?

[Luck, Tony]

>The current task pointers are identity mapped memory addresses.
>I shift them to the right by 12 bits (these bits are always 0-s).
>In that way, addresses up to 16 Tbytes can fit into the lock word.

Neat trick.  Will work for most people ... but watch out if you
have an architecture that has sparse physical address space and
can thus potentially allocate a task structure on a 16TB boundary.

At first I thought SGI Altix could be hurt by this, but they are
saved by the fact that bits [37:36] are always set to one.

I know of at least one 1TB machine now, so 16TB machines are only
a few years away.  You could stretch the life of this patch by
using PAGE_SHIFT, rather than 12 (as practically nobody builds
kernels with a 4k pagesize, especially not on monster machines).

Or perhaps just fix the allocation of task structures to skip
around the 16TB aligned ones?

-Tony

Re: Who owns those locks ?

[Zoltan Menyhart]

"Luck, Tony" wrote:
> 
> >The current task pointers are identity mapped memory addresses.
> >I shift them to the right by 12 bits (these bits are always 0-s).
> >In that way, addresses up to 16 Tbytes can fit into the lock word.
> 
> Neat trick.  Will work for most people ... but watch out if you
> have an architecture that has sparse physical address space and
> can thus potentially allocate a task structure on a 16TB boundary.
> 
> At first I thought SGI Altix could be hurt by this, but they are
> saved by the fact that bits [37:36] are always set to one.
> 
> I know of at least one 1TB machine now, so 16TB machines are only
> a few years away.  You could stretch the life of this patch by
> using PAGE_SHIFT, rather than 12 (as practically nobody builds
> kernels with a 4k pagesize, especially not on monster machines).
> 
> Or perhaps just fix the allocation of task structures to skip
> around the 16TB aligned ones?
> 
> -Tony

The first reason to use a shift of 12 bits is:
you can see easily what the address of the owner's task structure is.
In addition, with page size of 16 Kbytes, you've got only 16 Tbytes
in the identity mapped kernel address space any way.
Should we move to a page size of 64 Kbytes, you can use a shift of
16 bits and you keep the address human readable ;-)

Thanks,

Zoltán

RE: Who owns those locks ?

[Luck, Tony]

>The first reason to use a shift of 12 bits is:
>you can see easily what the address of the owner's task structure is.
>In addition, with page size of 16 Kbytes, you've got only 16 Tbytes
>in the identity mapped kernel address space any way.
>Should we move to a page size of 64 Kbytes, you can use a shift of
>16 bits and you keep the address human readable ;-)

Human readable is nice.

The identity mapped kernel space is not limited by the pagesize.
Mappings in region 7[*] are provided by the Alt-dtlb miss handler,
which just inserts a kernel granule sized mapping into the TLB
to cover any TLB miss.

-Tony

[*] except for the percpu area in the top 64k of region 7 which is
mapped by a locked entry in a DTR register.

Re: Who owns those locks ?

[Anton Blanchard]

> Why don't you put the ID of the owner of the lock in the lock word ?
> Here is your patch for IA-64.
> Doesn't cost any additional instruction, you can have it in your
> "production" kernel, too.

We already do this on ppc64.

Anton

Re: Who owns those locks ?

[Bjorn Helgaas]

On Wednesday 12 May 2004 3:56 am, Zoltan Menyhart wrote:
> Got a dead lock ?
> No idea how you got there ?
> 
> Why don't you put the ID of the owner of the lock in the lock word ?
> Here is your patch for IA-64.
> Doesn't cost any additional instruction, you can have it in your
> "production" kernel, too.

Whatever happened with this patch?  I really like the idea, but
it seems like it died on the vine.  Maybe it's time to clean it
up, pull all the bits together, and repost it.

Re: Who owns those locks ?

[Zoltan Menyhart]

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

Bjorn Helgaas wrote:
> 
> On Wednesday 12 May 2004 3:56 am, Zoltan Menyhart wrote:
> > Got a dead lock ?
> > No idea how you got there ?
> >
> > Why don't you put the ID of the owner of the lock in the lock word ?
> > Here is your patch for IA-64.
> > Doesn't cost any additional instruction, you can have it in your
> > "production" kernel, too.
> 
> Whatever happened with this patch?  I really like the idea, but
> it seems like it died on the vine.  Maybe it's time to clean it
> up, pull all the bits together, and repost it.

Here you are.
(I'm still playing with 2.6.5)

Zoltán Menyhárt

[-- Attachment #2: l --]
[-- Type: text/plain, Size: 3360 bytes --]

--- 2.6.5.ref/include/asm-ia64/spinlock.h	Sun Apr  4 05:36:17 2004
+++ 2.6.5.new/include/asm-ia64/spinlock.h	Wed May 12 13:17:50 2004
@@ -45,7 +45,8 @@
 	asm volatile ("{\n\t"
 		      "  mov ar.ccv = r0\n\t"
 		      "  mov r28 = ip\n\t"
-		      "  mov r30 = 1;;\n\t"
+		      /* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "}\n\t"
 		      "cmpxchg4.acq r30 = [%1], r30, ar.ccv\n\t"
 		      "movl r29 = ia64_spinlock_contention_pre3_4;;\n\t"
@@ -57,7 +58,8 @@
 	asm volatile ("{\n\t"
 		      "  mov ar.ccv = r0\n\t"
 		      "  mov r28 = ip\n\t"
-		      "  mov r30 = 1;;\n\t"
+		      /* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "}\n\t"
 		      "cmpxchg4.acq r30 = [%1], r30, ar.ccv;;\n\t"
 		      "cmp4.ne p14, p0 = r30, r0\n"
@@ -68,7 +70,8 @@
 # ifdef CONFIG_ITANIUM
 	/* don't use brl on Itanium... */
 	/* mis-declare, so we get the entry-point, not it's function descriptor: */
-	asm volatile ("mov r30 = 1\n\t"
+	asm volatile (/* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "mov ar.ccv = r0;;\n\t"
 		      "cmpxchg4.acq r30 = [%0], r30, ar.ccv\n\t"
 		      "movl r29 = ia64_spinlock_contention;;\n\t"
@@ -77,7 +80,8 @@
 		      "(p14) br.call.spnt.many b6 = b6"
 		      : "=r"(ptr) : "r"(ptr) : IA64_SPINLOCK_CLOBBERS);
 # else
-	asm volatile ("mov r30 = 1\n\t"
+	asm volatile (/* "  mov r30 = 1;;\n\t" */
+		      "  shr.u r30 = r13, 12;;\n\t"	/* Current task pointer */
 		      "mov ar.ccv = r0;;\n\t"
 		      "cmpxchg4.acq r30 = [%0], r30, ar.ccv;;\n\t"
 		      "cmp4.ne p14, p0 = r30, r0\n\t"
@@ -89,14 +93,17 @@
 #else /* !ASM_SUPPORTED */
 # define _raw_spin_lock(x)								\
 do {											\
-	__u32 *ia64_spinlock_ptr = (__u32 *) (x);					\
-	__u64 ia64_spinlock_val;							\
-	ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr, 1, 0);			\
+	__u32	*ia64_spinlock_ptr = (__u32 *) (x);					\
+	__u64	ia64_spinlock_val;							\
+	__u32	new_spinlock_val = (__u32)((__u64) current >> 12);			\
+											\
+	ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr, new_spinlock_val, 0);	\
 	if (unlikely(ia64_spinlock_val)) {						\
 		do {									\
 			while (*ia64_spinlock_ptr)					\
 				ia64_barrier();						\
-			ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr, 1, 0);	\
+			ia64_spinlock_val = ia64_cmpxchg4_acq(ia64_spinlock_ptr,	\
+								new_spinlock_val, 0);	\
 		} while (ia64_spinlock_val);						\
 	}										\
 } while (0)
@@ -104,7 +111,7 @@
 
 #define spin_is_locked(x)	((x)->lock != 0)
 #define _raw_spin_unlock(x)	do { barrier(); ((spinlock_t *) x)->lock = 0; } while (0)
-#define _raw_spin_trylock(x)	(cmpxchg_acq(&(x)->lock, 0, 1) == 0)
+#define _raw_spin_trylock(x)	(cmpxchg_acq(&(x)->lock, 0, (__u32)((__u64) current >> 12)) == 0)
 #define spin_unlock_wait(x)	do { barrier(); } while ((x)->lock)
 
 typedef struct {
--- 2.6.5.ref/arch/ia64/kernel/head.S	Wed Apr 21 16:18:26 2004
+++ 2.6.5.new/arch/ia64/kernel/head.S	Wed May 12 16:31:33 2004
@@ -917,7 +917,8 @@
 	ld4 r30=[r31]		// don't use ld4.bias; if it's contended, we won't write the word
 	;;
 	cmp4.ne p14,p0=r30,r0
-	mov r30 = 1
+//	mov r30 = 1
+	shr.u r30 = r13, 12	// Current task pointer
 (p14)	br.cond.sptk.few .wait
 	;;
 	cmpxchg4.acq r30=[r31], r30, ar.ccv

Re: Who owns those locks ?

[Bjorn Helgaas]

On Monday 07 June 2004 2:58 am, Zoltan Menyhart wrote:
> Bjorn Helgaas wrote:
> > On Wednesday 12 May 2004 3:56 am, Zoltan Menyhart wrote:
> > > Got a dead lock ?
> > > No idea how you got there ?
> > >
> > > Why don't you put the ID of the owner of the lock in the lock word ?
> > > Here is your patch for IA-64.
> > > Doesn't cost any additional instruction, you can have it in your
> > > "production" kernel, too.
> > 
> > Whatever happened with this patch?  I really like the idea, but
> > it seems like it died on the vine.  Maybe it's time to clean it
> > up, pull all the bits together, and repost it.
> 
> Here you are.
> (I'm still playing with 2.6.5)

There are a couple issues I was thinking of when
I wrote "clean it up, pull the bits together...":

	1) Tony Luck's question about what happens when
	   "shr.u r30 = r13, 12" yields zero in the 32-bit
	   lock value.  I'm not the 2.6 maintainer, but I'd
	   sure like to see some solution for this.  It would
	   be a nightmare to debug a system where one random
	   task didn't release locks correctly.  Since other
	   arches use a trick like this, I'm hoping they've
	   figured out something we can copy (I haven't looked).

	2) A nit-pick, but for things like this:

-                     "  mov r30 = 1;;\n\t"
+                     /* "  mov r30 = 1;;\n\t" */
+                     "  shr.u r30 = r13, 12;;\n\t"     /* Current task pointer */

	   just remove the old line, don't comment it out.

Thanks for collecting the bits.  I looked at it last week, got
derailed trying to figure out how the pre-gcc-3.3 lock contention
code worked (a comment there would have been helpful), and got
distracted.

Re: Who owns those locks ?

[Zoltan Menyhart]

Bjorn Helgaas wrote:
> 
> There are a couple issues I was thinking of when
> I wrote "clean it up, pull the bits together...":
> 
>         1) Tony Luck's question about what happens when
>            "shr.u r30 = r13, 12" yields zero in the 32-bit
>            lock value.  I'm not the 2.6 maintainer, but I'd
>            sure like to see some solution for this.  It would
>            be a nightmare to debug a system where one random
>            task didn't release locks correctly.  Since other
>            arches use a trick like this, I'm hoping they've
>            figured out something we can copy (I haven't looked).

Sure, I did not want to make an error like saying:
"640 K ought to be enough for everyone".

I'm afraid, there is no perfect solution.

- We do not want to change the lock size to 64 bits, do we ?
  -- Couple of new alignment problems.

- You keep my code, it is correct for a memory size up to 16 Tbytes.

- You shift by PAGE_SHIFT, rather than by 12 (using page size of
  16 Kbytes) => up to  64 Tbytes.
  -- Not that much human readable lock values.

- You move to PAGE_SIZE = 64 K, you get human readable lock values
  up to 256 Tbytes.

- You could store the "PID | miraculous bit" (to avoid PID = 0
  problem).
  -- Somewhat longer code.

I expect the main stream IA64 kernel to move to PAGE_SIZE = 64 K by
the time there will be machines with more than 16 Tbytes of memory
(as the processors have got just a very limited number of
translation look aside buffer entries, and the ever growing
application / memory sizes result in higher TLB miss rate unless the
page size increases).


Regards,

Zoltán

Re: Who owns those locks ?

[Bjorn Helgaas]

On Tuesday 08 June 2004 2:03 am, Zoltan Menyhart wrote:
> - You keep my code, it is correct for a memory size up to 16 Tbytes.

Many if not most large machines have sparse address spaces,
so you may have memory at an address that will cause a
problem even if the actual amount of memory is much smaller.

The main point is that I wouldn't want a time bomb that
will silently fail when somebody happens to boot on such
a machine.  Whether that's avoided by a "miraculous" bit,
throwing away problem pages at boot-time, avoiding task
allocation at specific addresses, etc.,  is secondary.

Re: Who owns those locks ?

[Zoltan Menyhart]

Bjorn Helgaas wrote:
> 
> On Tuesday 08 June 2004 2:03 am, Zoltan Menyhart wrote:
> > - You keep my code, it is correct for a memory size up to 16 Tbytes.
> 
> Many if not most large machines have sparse address spaces,
> so you may have memory at an address that will cause a
> problem even if the actual amount of memory is much smaller.
> 
> The main point is that I wouldn't want a time bomb that
> will silently fail when somebody happens to boot on such
> a machine.  Whether that's avoided by a "miraculous" bit,
> throwing away problem pages at boot-time, avoiding task
> allocation at specific addresses, etc.,  is secondary.

I see.
No use to make it too much complicated.
There is always the option CONFIG_DEBUG_SPINLOCK.

On our no-more-than-512-Gbyte-machine, this small stuff
"saved my life" twice.
I just wanted to share it...

Regards,

Zoltán