[PATCH] task_struct colouring ...

[PATCH] task_struct colouring ...

[Davide Libenzi]

Looking at both the Manfred and Fujitsu patches I propose this new version
for task struct colouring.
The patch from Manfred is too architecture dependent ( cr2 ) and storing
extra stuff in CPU registers is not IMHO a good idea.
This patch uses the basic idea of Fujitsu and improve it in two ways :

1) Speed

The patch from Fujitsu, besides other bitwise operations perform one store
( bad ) and one load memory access at every get current call :

 #define GET_CURRENT(reg) \
        movl $-8192, reg; \
        andl %esp, reg
        andl %esp, reg; \
        pushl reg; \
        shrl $13, reg; \
        andl $0x00000060, reg; \
        orl  0(%esp), reg; \
        addl $4, %esp

while this one perform only one load and less accessory ops :

 #define GET_CURRENT(reg) \
        movl $-8192, reg; \
        andl %esp, reg
        andl %esp, reg; \
        movl (reg), reg;

2) Code clarity

The patch from Fujitsu spread task pointer math through different files
while this one only inside arch/???/kernel/process.c :

struct task_struct *alloc_task_struct(void)
{
       unsigned long tskb = __get_free_pages(GFP_KERNEL, 1), tsk;
       tsk = tskb | ((tskb >> 13) & 0x00000060) | SMP_CACHE_BYTES;
       *(unsigned long *) tskb = tsk;
       return (struct task_struct *) tsk;
}

More, in finding the pointer directly at the base (SP & ~8191UL) makes it
easy for external programs ( ie gdb ) to seek the task_struct w/out
knowing the internal math that created it.
I've not benchmarked the patch yet, so help from guys with big SMP
machines and more L2 than the main memory I had in my PC until 5 years
ago, is welcome :)



PS: The patch is for x86 but it's architecture independence ( beside the
cache line size and bits ) will make it easy to port to other CPUs



- Davide




diff -Nru linux-2.5.0.vanilla/arch/i386/kernel/entry.S linux-2.5.0.chax/arch/i386/kernel/entry.S
--- linux-2.5.0.vanilla/arch/i386/kernel/entry.S	Fri Nov  2 17:18:49 2001
+++ linux-2.5.0.chax/arch/i386/kernel/entry.S	Fri Nov 30 11:13:46 2001
@@ -130,7 +130,8 @@

 #define GET_CURRENT(reg) \
 	movl $-8192, reg; \
-	andl %esp, reg
+	andl %esp, reg;	\
+	movl (reg), reg;

 ENTRY(lcall7)
 	pushfl			# We get a different stack layout with call gates,
@@ -144,7 +145,7 @@
 	movl %ecx,CS(%esp)	#
 	movl %esp,%ebx
 	pushl %ebx
-	andl $-8192,%ebx	# GET_CURRENT
+	GET_CURRENT(%ebx)
 	movl exec_domain(%ebx),%edx	# Get the execution domain
 	movl 4(%edx),%edx	# Get the lcall7 handler for the domain
 	pushl $0x7
@@ -165,7 +166,7 @@
 	movl %ecx,CS(%esp)	#
 	movl %esp,%ebx
 	pushl %ebx
-	andl $-8192,%ebx	# GET_CURRENT
+	GET_CURRENT(%ebx)
 	movl exec_domain(%ebx),%edx	# Get the execution domain
 	movl 4(%edx),%edx	# Get the lcall7 handler for the domain
 	pushl $0x27
diff -Nru linux-2.5.0.vanilla/arch/i386/kernel/init_task.c linux-2.5.0.chax/arch/i386/kernel/init_task.c
--- linux-2.5.0.vanilla/arch/i386/kernel/init_task.c	Mon Sep 17 15:29:09 2001
+++ linux-2.5.0.chax/arch/i386/kernel/init_task.c	Fri Nov 30 13:18:23 2001
@@ -20,7 +20,13 @@
  */
 union task_union init_task_union
 	__attribute__((__section__(".data.init_task"))) =
-		{ INIT_TASK(init_task_union.task) };
+		{
+			{
+				tskptr: (unsigned long) &init_task_union.x.task ,
+				__cachepad: { 0, },
+				task: INIT_TASK(init_task_union.x.task)
+			}
+		};

 /*
  * per-CPU TSS segments. Threads are completely 'soft' on Linux,
diff -Nru linux-2.5.0.vanilla/arch/i386/kernel/process.c linux-2.5.0.chax/arch/i386/kernel/process.c
--- linux-2.5.0.vanilla/arch/i386/kernel/process.c	Thu Oct  4 18:42:54 2001
+++ linux-2.5.0.chax/arch/i386/kernel/process.c	Fri Nov 30 13:12:46 2001
@@ -581,7 +581,7 @@
 {
 	struct pt_regs * childregs;

-	childregs = ((struct pt_regs *) (THREAD_SIZE + (unsigned long) p)) - 1;
+	childregs = ((struct pt_regs *) (THREAD_SIZE + ((unsigned long) p & ~8191UL))) - 1;
 	struct_cpy(childregs, regs);
 	childregs->eax = 0;
 	childregs->esp = esp;
@@ -821,3 +821,18 @@
 }
 #undef last_sched
 #undef first_sched
+
+
+struct task_struct *alloc_task_struct(void)
+{
+	unsigned long tskb = __get_free_pages(GFP_KERNEL, 1), tsk;
+	tsk = tskb | ((tskb >> 13) & 0x00000060) | SMP_CACHE_BYTES;
+	*(unsigned long *) tskb = tsk;
+	return (struct task_struct *) tsk;
+}
+
+void free_task_struct(struct task_struct *p)
+{
+	free_pages((unsigned long) (p) & ~8191UL, 1);
+}
+
diff -Nru linux-2.5.0.vanilla/arch/i386/lib/getuser.S linux-2.5.0.chax/arch/i386/lib/getuser.S
--- linux-2.5.0.vanilla/arch/i386/lib/getuser.S	Mon Jan 12 13:42:52 1998
+++ linux-2.5.0.chax/arch/i386/lib/getuser.S	Fri Nov 30 09:56:29 2001
@@ -29,6 +29,7 @@
 __get_user_1:
 	movl %esp,%edx
 	andl $0xffffe000,%edx
+	movl (%edx),%edx
 	cmpl addr_limit(%edx),%eax
 	jae bad_get_user
 1:	movzbl (%eax),%edx
@@ -42,6 +43,7 @@
 	movl %esp,%edx
 	jc bad_get_user
 	andl $0xffffe000,%edx
+	movl (%edx),%edx
 	cmpl addr_limit(%edx),%eax
 	jae bad_get_user
 2:	movzwl -1(%eax),%edx
@@ -55,6 +57,7 @@
 	movl %esp,%edx
 	jc bad_get_user
 	andl $0xffffe000,%edx
+	movl (%edx),%edx
 	cmpl addr_limit(%edx),%eax
 	jae bad_get_user
 3:	movl -3(%eax),%edx
diff -Nru linux-2.5.0.vanilla/include/asm-i386/current.h linux-2.5.0.chax/include/asm-i386/current.h
--- linux-2.5.0.vanilla/include/asm-i386/current.h	Fri Aug 14 16:35:22 1998
+++ linux-2.5.0.chax/include/asm-i386/current.h	Fri Nov 30 11:22:23 2001
@@ -5,9 +5,9 @@

 static inline struct task_struct * get_current(void)
 {
-	struct task_struct *current;
-	__asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
-	return current;
+	unsigned long *tskptr;
+	__asm__("andl %%esp,%0; ":"=r" (tskptr) : "0" (~8191UL));
+	return (struct task_struct *) *tskptr;
  }

 #define current get_current()
diff -Nru linux-2.5.0.vanilla/include/asm-i386/hw_irq.h linux-2.5.0.chax/include/asm-i386/hw_irq.h
--- linux-2.5.0.vanilla/include/asm-i386/hw_irq.h	Thu Nov 22 11:46:18 2001
+++ linux-2.5.0.chax/include/asm-i386/hw_irq.h	Fri Nov 30 12:11:16 2001
@@ -115,7 +115,8 @@

 #define GET_CURRENT \
 	"movl %esp, %ebx\n\t" \
-	"andl $-8192, %ebx\n\t"
+	"andl $-8192, %ebx\n\t" \
+	"movl (%ebx), %ebx\n\t"

 /*
  *	SMP has a few special interrupts for IPI messages
diff -Nru linux-2.5.0.vanilla/include/asm-i386/processor.h linux-2.5.0.chax/include/asm-i386/processor.h
--- linux-2.5.0.vanilla/include/asm-i386/processor.h	Thu Nov 22 11:46:19 2001
+++ linux-2.5.0.chax/include/asm-i386/processor.h	Fri Nov 30 13:06:00 2001
@@ -14,6 +14,7 @@
 #include <asm/types.h>
 #include <asm/sigcontext.h>
 #include <asm/cpufeature.h>
+#include <linux/kernel.h>
 #include <linux/cache.h>
 #include <linux/config.h>
 #include <linux/threads.h>
@@ -444,15 +445,18 @@
 }

 unsigned long get_wchan(struct task_struct *p);
-#define KSTK_EIP(tsk)	(((unsigned long *)(4096+(unsigned long)(tsk)))[1019])
-#define KSTK_ESP(tsk)	(((unsigned long *)(4096+(unsigned long)(tsk)))[1022])
+#define KSTK_EIP(tsk)	(((unsigned long *)(4096+(unsigned long)(tsk) & ~8191UL))[1019])
+#define KSTK_ESP(tsk)	(((unsigned long *)(4096+(unsigned long)(tsk) & ~8191UL))[1022])

 #define THREAD_SIZE (2*PAGE_SIZE)
-#define alloc_task_struct() ((struct task_struct *) __get_free_pages(GFP_KERNEL,1))
-#define free_task_struct(p) free_pages((unsigned long) (p), 1)
+
+
+extern struct task_struct *alloc_task_struct(void);
+extern void free_task_struct(struct task_struct *p);
+
 #define get_task_struct(tsk)      atomic_inc(&virt_to_page(tsk)->count)

-#define init_task	(init_task_union.task)
+#define init_task	(init_task_union.x.task)
 #define init_stack	(init_task_union.stack)

 struct microcode {
diff -Nru linux-2.5.0.vanilla/include/linux/sched.h linux-2.5.0.chax/include/linux/sched.h
--- linux-2.5.0.vanilla/include/linux/sched.h	Thu Nov 22 11:46:19 2001
+++ linux-2.5.0.chax/include/linux/sched.h	Fri Nov 30 13:07:19 2001
@@ -508,7 +508,11 @@
 #endif

 union task_union {
-	struct task_struct task;
+	struct {
+		unsigned long tskptr;
+		unsigned long __cachepad[SMP_CACHE_BYTES/sizeof(long) - 1];
+		struct task_struct task;
+	} x;
 	unsigned long stack[INIT_TASK_SIZE/sizeof(long)];
 };

Re: [PATCH] task_struct colouring ...

[Alan Cox]

> Looking at both the Manfred and Fujitsu patches I propose this new version
> for task struct colouring.
> The patch from Manfred is too architecture dependent ( cr2 ) and storing
> extra stuff in CPU registers is not IMHO a good idea.

Well the whole "current" handling is entirely architecture dependant anyway.
On most saner platforms current is a global register variable (the wonders
of gcc) and the whole problem simply isnt there

Re: [PATCH] task_struct colouring ...

[H. Peter Anvin]

Followup to:  <E169wL1-00052x-00@the-village.bc.nu>
By author:    Alan Cox <alan@lxorguk.ukuu.org.uk>
In newsgroup: linux.dev.kernel
>
> > Looking at both the Manfred and Fujitsu patches I propose this new version
> > for task struct colouring.
> > The patch from Manfred is too architecture dependent ( cr2 ) and storing
> > extra stuff in CPU registers is not IMHO a good idea.
> 
> Well the whole "current" handling is entirely architecture dependant anyway.
> On most saner platforms current is a global register variable (the wonders
> of gcc) and the whole problem simply isnt there
> 

Using %cr2 was pretty broken, but I liked the patch using %tr.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt	<amsp@zytor.com>

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Fri, 30 Nov 2001, Alan Cox wrote:

> > Looking at both the Manfred and Fujitsu patches I propose this new version
> > for task struct colouring.
> > The patch from Manfred is too architecture dependent ( cr2 ) and storing
> > extra stuff in CPU registers is not IMHO a good idea.
>
> Well the whole "current" handling is entirely architecture dependant anyway.
> On most saner platforms current is a global register variable (the wonders
> of gcc) and the whole problem simply isnt there

So You like the idea of stocking structure pointers inside CPU registers
or I missed Your point ?
The proposed implementation is "uniform" between architectures, that's my
point.
What for CPUs that cannot offer "free" registers ?
What if someone else, following the example, start stocking some other
pointer in free registers ?




- Davide

Re: [PATCH] task_struct colouring ...

[Alan Cox]

> So You like the idea of stocking structure pointers inside CPU registers
> or I missed Your point ?
> The proposed implementation is "uniform" between architectures, that's my
> point.

An uniform implementation for a totally non uniform set of processors. Not
actually useful. The x86 is one of the few cpus so short of registers that
current in a global register is not a win performancewise.

The cache behaviour also heavily depends on the processor. In paticular the
problem with having to align stacks to do current tricks is absent on non
x86 processors so they can use properly coloured stacks. 

current is far too critical to generalise

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Fri, 30 Nov 2001, Alan Cox wrote:

> > So You like the idea of stocking structure pointers inside CPU registers
> > or I missed Your point ?
> > The proposed implementation is "uniform" between architectures, that's my
> > point.
>
> An uniform implementation for a totally non uniform set of processors. Not
> actually useful. The x86 is one of the few cpus so short of registers that
> current in a global register is not a win performancewise.

The point is why store kernel pointers in global registers when You can
achieve the same functionality, with a smaller patch, that does not need
to be recoded for each CPU, without using global registers.



> The cache behaviour also heavily depends on the processor. In paticular the
> problem with having to align stacks to do current tricks is absent on non
> x86 processors so they can use properly coloured stacks.
>
> current is far too critical to generalise

This is the diff for current :

 static inline struct task_struct * get_current(void)
 {
-       struct task_struct *current;
-       __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
-       return current;
+       unsigned long *tskptr;
+       __asm__("andl %%esp,%0; ":"=r" (tskptr) : "0" (~8191UL));
+       return (struct task_struct *) *tskptr;
 }




- Davide

Re: [PATCH] task_struct colouring ...

[H. Peter Anvin]

Followup to:  <Pine.LNX.4.40.0111301614000.1600-100000@blue1.dev.mcafeelabs.com>
By author:    Davide Libenzi <davidel@xmailserver.org>
In newsgroup: linux.dev.kernel
> 
> The point is why store kernel pointers in global registers when You can
> achieve the same functionality, with a smaller patch, that does not need
> to be recoded for each CPU, without using global registers.
> 

Because global registers are faster!  This is exactly the kind of
stuff that is properly CPU-dependent and should be treated as such.
Heck, it even depends on what kind of multiprocessor architecture, if
any, you're using!

That being said, I belive that on most, if not all, processors, the
idea of having the pointer point not to "current" but to a per-CPU
memory area is *very* appealing, and a change that should be made
uniform unless it's a significant lose on some machines...

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt	<amsp@zytor.com>

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On 30 Nov 2001, H. Peter Anvin wrote:

> Followup to:  <Pine.LNX.4.40.0111301614000.1600-100000@blue1.dev.mcafeelabs.com>
> By author:    Davide Libenzi <davidel@xmailserver.org>
> In newsgroup: linux.dev.kernel
> >
> > The point is why store kernel pointers in global registers when You can
> > achieve the same functionality, with a smaller patch, that does not need
> > to be recoded for each CPU, without using global registers.
> >
>
> Because global registers are faster!  This is exactly the kind of
> stuff that is properly CPU-dependent and should be treated as such.
> Heck, it even depends on what kind of multiprocessor architecture, if
> any, you're using!
>
> That being said, I belive that on most, if not all, processors, the
> idea of having the pointer point not to "current" but to a per-CPU
> memory area is *very* appealing, and a change that should be made
> uniform unless it's a significant lose on some machines...

Again this is the  "current"  diff :

 static inline struct task_struct * get_current(void)
 {
-       struct task_struct *current;
-       __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
-       return current;
+       unsigned long *tskptr;
+       __asm__("andl %%esp,%0; ":"=r" (tskptr) : "0" (~8191UL));
+       return (struct task_struct *) *tskptr;
 }

that will probably resolve in something like:

movl %esp, %eax
andl $-8192, %eax
movl (%eax), %eax





- Davide

Re: [PATCH] task_struct colouring ...

[H. Peter Anvin]

Davide Libenzi wrote:

> 
> Again this is the  "current"  diff :
> 
>  static inline struct task_struct * get_current(void)
>  {
> -       struct task_struct *current;
> -       __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
> -       return current;
> +       unsigned long *tskptr;
> +       __asm__("andl %%esp,%0; ":"=r" (tskptr) : "0" (~8191UL));
> +       return (struct task_struct *) *tskptr;
>  }
> 
> that will probably resolve in something like:
> 
> movl %esp, %eax
> andl $-8192, %eax
> movl (%eax), %eax
> 


This seems to confuddle the idea of colouring the kernel stack.

	-hpa

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Fri, 30 Nov 2001, H. Peter Anvin wrote:

> Davide Libenzi wrote:
>
> >
> > Again this is the  "current"  diff :
> >
> >  static inline struct task_struct * get_current(void)
> >  {
> > -       struct task_struct *current;
> > -       __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
> > -       return current;
> > +       unsigned long *tskptr;
> > +       __asm__("andl %%esp,%0; ":"=r" (tskptr) : "0" (~8191UL));
> > +       return (struct task_struct *) *tskptr;
> >  }
> >
> > that will probably resolve in something like:
> >
> > movl %esp, %eax
> > andl $-8192, %eax
> > movl (%eax), %eax
> >
>
>
> This seems to confuddle the idea of colouring the kernel stack.

It's task_truct colouring not stack, to colour the stack you've to go in
arch/??/kernel/process.c and jitter the stack pointer.
The task_struct colouring is done at task_struct creation time :


+struct task_struct *alloc_task_struct(void)
+{
+       unsigned long tskb = __get_free_pages(GFP_KERNEL, 1), tsk;
+       tsk = tskb | ((tskb >> 13) & 0x00000060) | SMP_CACHE_BYTES;
+       *(unsigned long *) tskb = tsk;
+       return (struct task_struct *) tsk;
+}




- Davide

Re: [PATCH] task_struct colouring ...

[H. Peter Anvin]

Davide Libenzi wrote:

>>
>>This seems to confuddle the idea of colouring the kernel stack.
>>
> 
> It's task_truct colouring not stack, to colour the stack you've to go in
> arch/??/kernel/process.c and jitter the stack pointer.
> The task_struct colouring is done at task_struct creation time :
> 
> +struct task_struct *alloc_task_struct(void)
> +{
> +       unsigned long tskb = __get_free_pages(GFP_KERNEL, 1), tsk;
> +       tsk = tskb | ((tskb >> 13) & 0x00000060) | SMP_CACHE_BYTES;
> +       *(unsigned long *) tskb = tsk;
> +       return (struct task_struct *) tsk;
> +}
> 


I know, but I believe the part of the idea was to color not just the
current, but also the stack.

Your idea would make the obvious way to color the kernel stack -- have the
stacks offset by a non-power-of-two -- no longer work.

	-hpa

Re: [PATCH] task_struct colouring ...

[Alan Cox]

> > movl %esp, %eax
> > andl $-8192, %eax
> > movl (%eax), %eax
> 
> This seems to confuddle the idea of colouring the kernel stack.

It means you cant offset the stacks but doesnt mean you can't jitter them.
If you pull the task out of the stack top you have another 1K or so free
to use to vary the initial %esp

Re: [PATCH] task_struct colouring ...

[Alan Cox]

> The point is why store kernel pointers in global registers when You can
> achieve the same functionality, with a smaller patch, that does not need
> to be recoded for each CPU, without using global registers.

Because it is much much much faster

Alan

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Sat, 1 Dec 2001, Alan Cox wrote:

> > The point is why store kernel pointers in global registers when You can
> > achieve the same functionality, with a smaller patch, that does not need
> > to be recoded for each CPU, without using global registers.
>
> Because it is much much much faster

We'll see how much faster is the global register allocation against code
like :

movl %esp, %eax
andl $-8192, %eax
movl (%eax), %eax

Because you can justify a global register allocation only if this "much
much faster" translates to a number that has sense.




- Davide

Re: [PATCH] task_struct colouring ...

[kumon]

Davide Libenzi writes:
 > On Sat, 1 Dec 2001, Alan Cox wrote:
 > > Because it is much much much faster
 > 
 > We'll see how much faster is the global register allocation against code
 > like :
 > 
 > movl %esp, %eax
 > andl $-8192, %eax
 > movl (%eax), %eax

Current should be much faster, if it is accessed very frequently.
If the frequency is high, the value is very likely being kept on L1
cache. If that's true, the access time is fast enough.
So, using indirection doesn't cause large penalty.

Apart from that, stack coloring is difficult. Recent CPUs use much
larger cache block, coloring needs big room in the stack area.
Pentium4 is said using 64B block, but actually it is sectored cache
within 128B block.
1KB room for stack coloring realizes only 8 colors.
--
Kouichi Kumon, Software Laboratory, Fujitsu Labs.
kumon@flab.fujitsu.co.jp

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Sun, 2 Dec 2001 kumon@flab.fujitsu.co.jp wrote:

> Davide Libenzi writes:
>  > On Sat, 1 Dec 2001, Alan Cox wrote:
>  > > Because it is much much much faster
>  >
>  > We'll see how much faster is the global register allocation against code
>  > like :
>  >
>  > movl %esp, %eax
>  > andl $-8192, %eax
>  > movl (%eax), %eax
>
> Current should be much faster, if it is accessed very frequently.
> If the frequency is high, the value is very likely being kept on L1
> cache. If that's true, the access time is fast enough.
> So, using indirection doesn't cause large penalty.
>
> Apart from that, stack coloring is difficult. Recent CPUs use much
> larger cache block, coloring needs big room in the stack area.
> Pentium4 is said using 64B block, but actually it is sectored cache
> within 128B block.
> 1KB room for stack coloring realizes only 8 colors.

true, that's why I'm using the Manfred idea of a separate allocation of
task structs through a slab allocator ( with task struct pointer stored at
stack base ) + init stack pointer jittering.
true even that with 128 bytes you'll get 8 colors in 1Kb, but 8 colors are
about 1/8 collision.




- Davide

Re: [PATCH] task_struct colouring ...

[Alan Cox]

> > 1KB room for stack coloring realizes only 8 colors.
> 
> true, that's why I'm using the Manfred idea of a separate allocation of
> task structs through a slab allocator ( with task struct pointer stored at

8 colours is probably enough. Especially once the scheduler is replaced by
something resembling sanity, that doesn't keep walking the entire runnable
list.

Re: [PATCH] task_struct colouring ...

[[MOc]cda*mirabilos]

> movl %esp, %eax
> andl $-8192, %eax
> movl (%eax), %eax

Although I'm good in assembly but bad in gas,
do you consider the middle line good style?

Binary AND with a negative decimal number?

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Sun, 2 Dec 2001, [MOc]cda*mirabilos wrote:

> > movl %esp, %eax
> > andl $-8192, %eax
> > movl (%eax), %eax
>
> Although I'm good in assembly but bad in gas,
> do you consider the middle line good style?
>
> Binary AND with a negative decimal number?

~N = -(N + 1)




- Davide

Re: [PATCH] task_struct colouring ...

[[MOc]cda*mirabilos]

> > > movl %esp, %eax
> > > andl $-8192, %eax
> > > movl (%eax), %eax
> >
> > Although I'm good in assembly but bad in gas,
> > do you consider the middle line good style?
> >
> > Binary AND with a negative decimal number?
> 
> ~N = -(N + 1)

I know, but I don't consider this good style, as
decimal arithmetic is for humans, and binary
{arithmetic,ops} are for the PC.

Please don't Cc: me, I read the list, thanks.

Thorsten

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Sun, 2 Dec 2001, [MOc]cda*mirabilos wrote:

> > > > movl %esp, %eax
> > > > andl $-8192, %eax
> > > > movl (%eax), %eax
> > >
> > > Although I'm good in assembly but bad in gas,
> > > do you consider the middle line good style?
> > >
> > > Binary AND with a negative decimal number?
> >
> > ~N = -(N + 1)
>
> I know, but I don't consider this good style, as
> decimal arithmetic is for humans, and binary
> {arithmetic,ops} are for the PC.

The better solution would be (STACK_SIZE - 1) but it's still decimal.



- Davide

Re: [PATCH] task_struct colouring ...

[Thorsten Glaser]

Dixitur de Davide Libenzi respondebo ad:
> > > > > movl %esp, %eax
> > > > > andl $-8192, %eax
> > > > > movl (%eax), %eax
> > > >
> > > > Although I'm good in assembly but bad in gas,
> > > > do you consider the middle line good style?
> > > >
> > > > Binary AND with a negative decimal number?
> > >
> > > ~N = -(N + 1)
> >
> > I know, but I don't consider this good style, as
> > decimal arithmetic is for humans, and binary
> > {arithmetic,ops} are for the PC.
>
> The better solution would be (STACK_SIZE - 1) but it's still decimal.

I agree on that, it's way more readable.

Please don't think that I'm flaming here, it's just that
a) we have a discussion on coding style
b) we don't (?) have an assembly coding style
c) gas is ugly anyway
d) but this seems really... unused

Sorry if I have offended you.

-mirabilos
-- 
C:\>debug
-e100 FA EB FC
-g
Pssssst... Don't tell anyone I'm free.......

Re: [PATCH] task_struct colouring ...

[Manfred Spraul]

>
> 2) Code clarity
>
I really liked Ben's idea of an include file with macros for asm access to the current pointer.
That was a major improvement for the code clarity. IMHO a patch that changes current
should introduce such a file.

>       unsigned long tskb = __get_free_pages(GFP_KERNEL, 1), tsk;
>      tsk = tskb | ((tskb >> 13) & 0x00000060) | SMP_CACHE_BYTES;
>      *(unsigned long *) tskb = tsk;

You only colour 2 bits (offset 32, 64 or 96 - all within one cacheline on P 4) - I doubt that this
helps a lot. And you do not colour the stack top - all processes sleeping in accept() will still
have their wait queues at the same cache colour. And if you use more bits, you risk
stack overflows.

Which means there are only 2 options for the memory allocation:
- split stack and task structure into 2 independant parts. task struct from slab, stack
    8 kB-colouring.
- switch to 16 kB allocations for stack+task, and then colour both stack and task
    structure.

There are obviously lots of alternatives how to look up the task structure address:
* bottom of stack allocation (your patch)
* %cr2 (broken, only works for OS' that never cause page faults such as Netware)
* gs: (segment register, x86-64 uses that. But i386 doesn't have the swapgs instruction)
* str (Ben's patch)
* read from local apic memory (real slow!, uncached memory reference)

> More, in finding the pointer directly at the base (SP & ~8191UL) makes it
> easy for external programs ( ie gdb ) to seek the task_struct w/out
> knowing the internal math that created it.

Is that a realistic problem? Usually you want to go from task struct to the stack, not the other
way around.

--
    Manfred

Re: [PATCH] task_struct colouring ...

[Davide Libenzi]

On Sat, 1 Dec 2001, Manfred Spraul wrote:

> >
> > 2) Code clarity
> >
> I really liked Ben's idea of an include file with macros for asm access to the current pointer.
> That was a major improvement for the code clarity. IMHO a patch that changes current
> should introduce such a file.
>
> >       unsigned long tskb = __get_free_pages(GFP_KERNEL, 1), tsk;
> >      tsk = tskb | ((tskb >> 13) & 0x00000060) | SMP_CACHE_BYTES;
> >      *(unsigned long *) tskb = tsk;
>
> You only colour 2 bits (offset 32, 64 or 96 - all within one cacheline on P 4) - I doubt that this
> helps a lot. And you do not colour the stack top - all processes sleeping in accept() will still
> have their wait queues at the same cache colour. And if you use more bits, you risk
> stack overflows.

32, 64, 96 and 128
Anyway it's clear that this is a 32 cache line size setup and that such
magic numbers have to change accounding to cache line size and
associativity level.
True that with CPUs with 7 or more bits for cache line size we're going to
be subject of stack overflow.
More then increasing stack allocation i'd rather prefer to allocate two
items ( like your patch ) 1) the task_struct from a slab 2) the stack with
__get_free_pages().
What I do not really like is storing pointers inside global CPU registers,
at least until the perf difference will justify it ( we'll see ).
The stack jittering is quite easy to implement in arch/??/kernel/process.c
and another couple of fixes.
I'll try slab task struct allocation + stack base pointer indirection.





- Davide

Re: [PATCH] task_struct colouring ...

[H. Peter Anvin]

Followup to:  <000901c17a51$62526070$010411ac@local>
By author:    "Manfred Spraul" <manfred@colorfullife.com>
In newsgroup: linux.dev.kernel
> 
> There are obviously lots of alternatives how to look up the task structure address:
> * bottom of stack allocation (your patch)
> * %cr2 (broken, only works for OS' that never cause page faults such as Netware)
> * gs: (segment register, x86-64 uses that. But i386 doesn't have the swapgs instruction)
> * str (Ben's patch)
> * read from local apic memory (real slow!, uncached memory reference)
> 

%gs on x86-64 actually points to a per-CPU area; as does the proposed
%tr hack.  IMNSHO I think this is a much better idea than having
something that points to "current"; if we do this consistently across
architectures I'm sure there is plenty we can use this per-CPU area
for.

Saving and restoring %gs (or %fs, which is less likely to be used in
userspace, and therefore potentially faster) is probably not
justifiable unless we do at least four accesses to "current" in the
average system call.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt	<amsp@zytor.com>