2.5isms
Subsystems (4)
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
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?
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));
#endifCan 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
@@ -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(strucreturn 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
@@ -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
@@ -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
@@ -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
@@ -390,7 +390,12 @@ int setup_arg_pages(struct linux_binprmwhile (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
@@ -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
@@ -71,6 +71,9 @@ extern __u32 secure_tcpv6_sequence_numbeextern 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
@@ -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
@@ -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);
Quoted 18 lines · Nick Piggin
Quoted 7 lines · Justin Pryzby
Hi all, I have more 2.5isms for the list.
./fs/binfmt_elf.c:
#ifdefCONFIG_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
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:
#ifdefCONFIG_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
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.
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
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.
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