Skip to contentSkip to conversation

2.5isms

DISCUSSION Justin Pryzby 4 participants 9 messages Dec 31, 2004 – Jan 3, 2005

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

Hi all, I have more 2.5isms for the list. ./fs/binfmt_elf.c:

#ifdef CONFIG_X86_HT
/*
* In some cases (e.g. Hyper-Threading), we want to avoid L1
* evictions by the processes running on the same package. One
* thing we can do is to shuffle the initial stack for them. *
* The conditionals here are unneeded, but kept in to make the
* code behaviour the same as pre change unless we have
* hyperthreaded processors. This should be cleaned up
* before 2.6
*/

if (smp_num_siblings > 1)
STACK_ALLOC(p, ((current->pid % 64) << 7));
#endif

Happy y2k5,
Justin

#1 lore raw
Quoted 14 lines · Justin Pryzby

Hi all, I have more 2.5isms for the list. ./fs/binfmt_elf.c:

#ifdef CONFIG_X86_HT
/*
* In some cases (e.g. Hyper-Threading), we want to avoid L1
* evictions by the processes running on the same package. One
* thing we can do is to shuffle the initial stack for them. *
* The conditionals here are unneeded, but kept in to make the
* code behaviour the same as pre change unless we have
* hyperthreaded processors. This should be cleaned up
* before 2.6
*/

Quoted 4 lines

if (smp_num_siblings > 1)
STACK_ALLOC(p, ((current->pid % 64) << 7));
#endif

Can we just kill it? Or do it unconditionally? Or maybe better yet, wrap it properly in arch code?

#2 lore raw
Quoted 15 lines · Nick Piggin
Quoted 14 lines · Justin Pryzby

Hi all, I have more 2.5isms for the list. ./fs/binfmt_elf.c:

#ifdef CONFIG_X86_HT
/*
* In some cases (e.g. Hyper-Threading), we want to avoid L1
* evictions by the processes running on the same package. One
* thing we can do is to shuffle the initial stack for them. *
* The conditionals here are unneeded, but kept in to make the
* code behaviour the same as pre change unless we have
* hyperthreaded processors. This should be cleaned up
* before 2.6
*/

Quoted 7 lines
Quoted 4 lines

if (smp_num_siblings > 1)
STACK_ALLOC(p, ((current->pid % 64) << 7));
#endif

Can we just kill it? Or do it unconditionally? Or maybe better yet, wrap it properly in arch code?

something like this perhaps?
http://www.kernel.org/pub/linux/kernel/people/arjan/execshield/00-
randomize-A0

although that randomizes more than just the stack pointer; the idea for just the stackpointer should be clear

arch/i386/kernel/process.c +27 -0
diff -purN linux-2.6.10-rc1/arch/i386/kernel/process.c linux-2.6.10-rc1-01-random/arch/i386/kernel/process.c
@@ -36,6 +36,8 @@
 #include <linux/module.h>
 #include <linux/kallsyms.h>
 #include <linux/ptrace.h>
+#include <linux/mman.h>
+#include <linux/random.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
@@ -805,3 +807,28 @@ asmlinkage int sys_get_thread_area(struc
 	return 0;
 }
 
+
+unsigned long arch_align_stack(unsigned long sp)
+{
+	if (current->flags & PF_RELOCEXEC)
+		sp -= ((get_random_int() % 65536) << 4);
+	return sp & ~0xf;
+}
+
+/*
+ * Generate random brk address between 128MB and 196MB. (if the layout
+ * allows it.)
+ */
+void randomize_brk(unsigned long old_brk)
+{
+	unsigned long new_brk, range_start, range_end;
+
+	range_start = 0x08000000;
+	if (current->mm->brk >= range_start)
+		range_start = current->mm->brk;
+	range_end = range_start + 0x02000000;
+	new_brk = randomize_range(range_start, range_end, 0);
+	if (new_brk)
+		current->mm->brk = new_brk;
+}
+
arch/ia64/ia32/binfmt_elf32.c +1 -1
diff -purN linux-2.6.10-rc1/arch/ia64/ia32/binfmt_elf32.c linux-2.6.10-rc1-01-random/arch/ia64/ia32/binfmt_elf32.c
@@ -256,7 +256,7 @@ elf32_set_personality (void)
 }
 
 static unsigned long
-elf32_map (struct file *filep, unsigned long addr, struct elf_phdr *eppnt, int prot, int type)
+elf32_map (struct file *filep, unsigned long addr, struct elf_phdr *eppnt, int prot, int type, unsigned long unused)
 {
 	unsigned long pgoff = (eppnt->p_vaddr) & ~IA32_PAGE_MASK;
 
arch/x86_64/ia32/ia32_binfmt.c +1 -1
diff -purN linux-2.6.10-rc1/arch/x86_64/ia32/ia32_binfmt.c linux-2.6.10-rc1-01-random/arch/x86_64/ia32/ia32_binfmt.c
@@ -386,7 +386,7 @@ int setup_arg_pages(struct linux_binprm 
 }
 
 static unsigned long
-elf32_map (struct file *filep, unsigned long addr, struct elf_phdr *eppnt, int prot, int type)
+elf32_map (struct file *filep, unsigned long addr, struct elf_phdr *eppnt, int prot, int type, unsigned long unused)
 {
 	unsigned long map_addr;
 	struct task_struct *me = current; 
drivers/char/random.c +27 -0
diff -purN linux-2.6.10-rc1/drivers/char/random.c linux-2.6.10-rc1-01-random/drivers/char/random.c
@@ -2453,3 +2453,30 @@ __u32 check_tcp_syn_cookie(__u32 cookie,
 	return (cookie - tmp[17]) & COOKIEMASK;	/* Leaving the data behind */
 }
 #endif
+
+/*
+ * Get a random word:
+ */
+unsigned int get_random_int(void)
+{
+	unsigned int val = 0;
+
+	val += current->pid + jiffies + (int)val;
+
+	/*
+	 * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
+	 * every second, from the entropy pool (and thus creates a limited
+	 * drain on it), and uses halfMD4Transform within the second. We
+	 * also spice it with the TSC (if available), jiffies, PID and the
+	 * stack address:
+	 */
+	return secure_ip_id(val);
+}
+
+unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len)
+{
+	unsigned long range = end - len - start;
+	if (end <= start + len)
+		return 0;
+	return PAGE_ALIGN(get_random_int() % range + start);
+}
fs/binfmt_elf.c +80 -33

211 lines not on this page · raw message

fs/exec.c +6 -0
diff -purN linux-2.6.10-rc1/fs/exec.c linux-2.6.10-rc1-01-random/fs/exec.c
@@ -390,7 +390,12 @@ int setup_arg_pages(struct linux_binprm 
 	while (i < MAX_ARG_PAGES)
 		bprm->page[i++] = NULL;
 #else
+#ifdef __HAVE_ARCH_ALIGN_STACK
+	stack_base = arch_align_stack(STACK_TOP - MAX_ARG_PAGES*PAGE_SIZE);
+	stack_base = PAGE_ALIGN(stack_base);
+#else
 	stack_base = STACK_TOP - MAX_ARG_PAGES * PAGE_SIZE;
+#endif
 	mm->arg_start = bprm->p + stack_base;
 	arg_size = STACK_TOP - (PAGE_MASK & (unsigned long) mm->arg_start);
 #endif
@@ -839,6 +844,7 @@ int flush_old_exec(struct linux_binprm *
 	tcomm[i] = '\0';
 	set_task_comm(current, tcomm);
 
+	current->flags &= ~PF_RELOCEXEC;
 	flush_thread();
 
 	if (bprm->e_uid != current->euid || bprm->e_gid != current->egid || 
include/asm-i386/elf.h +3 -0
diff -purN linux-2.6.10-rc1/include/asm-i386/elf.h linux-2.6.10-rc1-01-random/include/asm-i386/elf.h
@@ -190,4 +190,7 @@ do {									      \
 
 #endif
 
+#define __HAVE_ARCH_RANDOMIZE_BRK
+extern void randomize_brk(unsigned long old_brk);
+
 #endif
include/linux/random.h +3 -0
diff -purN linux-2.6.10-rc1/include/linux/random.h linux-2.6.10-rc1-01-random/include/linux/random.h
@@ -71,6 +71,9 @@ extern __u32 secure_tcpv6_sequence_numbe
 extern struct file_operations random_fops, urandom_fops;
 #endif
 
+unsigned int get_random_int(void);
+unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
+
 #endif /* __KERNEL___ */
 
 #endif /* _LINUX_RANDOM_H */
include/linux/resource.h +4 -1
diff -purN linux-2.6.10-rc1/include/linux/resource.h linux-2.6.10-rc1-01-random/include/linux/resource.h
@@ -52,8 +52,11 @@ struct rlimit {
 /*
  * Limit the stack by to some sane default: root can always
  * increase this limit if needed..  8MB seems reasonable.
+ *
+ * (2MB more to cover randomization effects.)
  */
-#define _STK_LIM	(8*1024*1024)
+#define _STK_LIM	(10*1024*1024)
+#define EXEC_STACK_BIAS	(2*1024*1024)
 
 /*
  * GPG wants 32kB of mlocked memory, to make sure pass phrases
include/linux/sched.h +1 -0
diff -purN linux-2.6.10-rc1/include/linux/sched.h linux-2.6.10-rc1-01-random/include/linux/sched.h
@@ -701,6 +701,7 @@ do { if (atomic_dec_and_test(&(tsk)->usa
 #define PF_LESS_THROTTLE 0x00100000	/* Throttle me less: I clean memory */
 #define PF_SYNCWRITE	0x00200000	/* I am doing a sync write */
 #define PF_BORROWED_MM	0x00400000	/* I am a kthread doing use_mm */
+#define PF_RELOCEXEC	0x00800000      /* randomize virtual address space */
 
 #ifdef CONFIG_SMP
 extern int set_cpus_allowed(task_t *p, cpumask_t new_mask);
#3 lore raw
In reply to Nick Piggin
Quoted 18 lines · Nick Piggin
Quoted 7 lines · Justin Pryzby

Hi all, I have more 2.5isms for the list. ./fs/binfmt_elf.c:
#ifdef CONFIG_X86_HT
/*
* In some cases (e.g. Hyper-Threading), we want to avoid L1
* evictions by the processes running on the same package. One
* thing we can do is to shuffle the initial stack for them. *

Quoted 9 lines

* The conditionals here are unneeded, but kept in to make the
* code behaviour the same as pre change unless we have
* hyperthreaded processors. This should be cleaned up
* before 2.6
*/
if (smp_num_siblings > 1)
STACK_ALLOC(p, ((current->pid % 64) << 7));
#endif

Quoted 2 lines

Can we just kill it? Or do it unconditionally? Or maybe better yet, wrap it properly in arch code?

You can't kill it without ruining performance on older HT CPUs. I would just keep it, it fixes the problem perhaps with a small amount of code. A more generalized #ifdef may be a good idea (NEED_STACK_RANDOM) may be a good idea, but it is not really a pressing need. Enabling it unconditionally may be an option, although it will make it harder to repeat test runs on non hyperthreaded CPUs.

-Andi

#4 lore raw
Quoted 22 lines · Andi Kleen
Quoted 19 lines · Nick Piggin
Quoted 16 lines · Justin Pryzby

Hi all, I have more 2.5isms for the list. ./fs/binfmt_elf.c:
#ifdef CONFIG_X86_HT
/*
* In some cases (e.g. Hyper-Threading), we want to avoid L1
* evictions by the processes running on the same package. One
* thing we can do is to shuffle the initial stack for them. *
* The conditionals here are unneeded, but kept in to make the
* code behaviour the same as pre change unless we have
* hyperthreaded processors. This should be cleaned up
* before 2.6
*/
if (smp_num_siblings > 1)
STACK_ALLOC(p, ((current->pid % 64) << 7));
#endif

Quoted 8 lines
Quoted 2 lines

Can we just kill it? Or do it unconditionally? Or maybe better yet, wrap it properly in arch code?

You can't kill it without ruining performance on older HT CPUs.
I would just keep it, it fixes the problem perhaps with a small amount of code. A more generalized #ifdef may be a good idea (NEED_STACK_RANDOM) may be a good idea, but it is not really a pressing need. Enabling it unconditionally may be an option, although it will make it harder to repeat test runs on non hyperthreaded CPUs.

Interesting. Yeah something like Arjan posted looks better then... having CONFIG_X86_HT in generic code is obviously pretty ugly.

I'm curious about a couple of points though. First, is that it is basically just adding a cache colouring to the stack, right? In that case why do only older HT CPUs have bad performance without it? And wouldn't it possibly make even non HT CPUs possibly slightly more efficient WRT caching the stacks of multiple processes?

Second, on what workloads does performance suffer, can you remember? I wonder if natural variations in the stack pointer as the program runs would mitigate the effect of this on all but micro benchmarks?

But even if that were so so, it seems simple enough that I don't have any real problem with keeping it of course.

Thanks,
Nick

#5 lore raw
Quoted 7 lines

I'm curious about a couple of points though. First, is that it is basically just adding a cache colouring to the stack, right? In that case why do only older HT CPUs have bad performance without it? And wouldn't it possibly make even non HT CPUs possibly slightly more efficient WRT caching the stacks of multiple processes?

it's a win on more than older HT cpus. It's just that those suffer it the most... (since there you have 2 "cpus" share the cache, meaning you get double the aliasing)

Quoted 3 lines

Second, on what workloads does performance suffer, can you remember? I wonder if natural variations in the stack pointer as the program runs would mitigate the effect of this on all but micro benchmarks?

one of the problem cases I remember is network daemons all waiting in accept() for connections. All from the same codepath basically. Randomizing the stackpointer is a gain for that on all cpus that have finite affinity on their caches.

Quoted 2 lines

But even if that were so so, it seems simple enough that I don't have any real problem with keeping it of course.

The reason my patch does it much more is that it makes it a step harder to write exploits for stack buffer overflows.

#6 lore raw
Quoted 18 lines · Arjan van de Ven
Quoted 5 lines

I'm curious about a couple of points though. First, is that it is basically just adding a cache colouring to the stack, right? In that case why do only older HT CPUs have bad performance without it? And wouldn't it possibly make even non HT CPUs possibly slightly more efficient WRT caching the stacks of multiple processes?

it's a win on more than older HT cpus. It's just that those suffer it the most... (since there you have 2 "cpus" share the cache, meaning you get double the aliasing)

Quoted 3 lines

Second, on what workloads does performance suffer, can you remember? I wonder if natural variations in the stack pointer as the program runs would mitigate the effect of this on all but micro benchmarks?

Quoted 5 lines

one of the problem cases I remember is network daemons all waiting in accept() for connections. All from the same codepath basically. Randomizing the stackpointer is a gain for that on all cpus that have finite affinity on their caches.

I see. Yes, that would be a prime candidate.

Quoted 10 lines
Quoted 4 lines

But even if that were so so, it seems simple enough that I don't have any real problem with keeping it of course.

The reason my patch does it much more is that it makes it a step harder to write exploits for stack buffer overflows.

Oh yeah I realised that. I just meant specifically the code to do arch specific stack colouring.

Thanks
Nick

#7 lore raw
In reply to Nick Piggin
Quoted 4 lines · Nick Piggin

I'm curious about a couple of points though. First, is that it is basically just adding a cache colouring to the stack, right? In that case why do only older HT CPUs have bad performance without it? And wouldn't it possibly make

Intel improved the HT implementation over time (there are at least three generations) In particular the latest "Prescott" CPUs lost a lot of problems earlier versions have. As far as I know they improved the caches to make the cache thrashing problem less severe.

Quoted 2 lines

even non HT CPUs possibly slightly more efficient WRT caching the stacks of multiple processes?

Not on x86 no because they normally have physically indexed caches (except for L1, but that is not really preserved over a context switch) HT is just a special case because two threads essentially share cache.

In theory it could help on non x86 CPUs with virtually indexed caches, but it is doubtful if they don't need more advanced forms of cache colouring.

Quoted 3 lines

Second, on what workloads does performance suffer, can you remember? I wonder if natural variations in the stack pointer as the program runs would mitigate the effect of this on all but micro benchmarks?

iirc on lots of different workloas that run code on both virtual CPUs at the same time. Without it you would get L1 cache thrashing, which can slow things down quite a lot.

And yes it made a real difference. The P4 cache have some pecularities ("64K aliasing") that made the problem worse.

-Andi

#8 lore raw
Quoted 6 lines · Andi Kleen
Quoted 2 lines · Nick Piggin

even non HT CPUs possibly slightly more efficient WRT caching the stacks of multiple processes?

Quoted 7 lines

Not on x86 no because they normally have physically indexed caches (except for L1, but that is not really preserved over a context switch) HT is just a special case because two threads essentially share cache.

In theory it could help on non x86 CPUs with virtually indexed caches, but it is doubtful if they don't need more advanced forms of cache colouring.

That makes sense. I wonder if those architectures may just want to implement it anyway. If this is such a win here, then it may be low hanging fruit for those architectures.

But I guess there is something fundamentally a bit different when you have two processes competing for L1 cache *at the same time*.

Quoted 6 lines
Quoted 4 lines

Second, on what workloads does performance suffer, can you remember? I wonder if natural variations in the stack pointer as the program runs would mitigate the effect of this on all but micro benchmarks?

Quoted 7 lines

iirc on lots of different workloas that run code on both virtual CPUs at the same time. Without it you would get L1 cache thrashing, which can slow things down quite a lot.

And yes it made a real difference. The P4 cache have some pecularities ("64K aliasing") that made the problem worse.

Interesting, thanks.