futex local DoS on most architectures
Subsystems (2)
The issue described in [1] is still present and unfixed (and even the fix there wasn't complete since it didn't cover SMP).
Thanks to Riku Voipio for noting that it is still unfixed.
cu
Adrian
Quoted 9 lines · Adrian Bunk
The issue described in [1] is still present and unfixed (and even the fix there wasn't complete since it didn't cover SMP).
Thanks to Riku Voipio for noting that it is still unfixed.
cu
Adrian
I think calling it a local DoS may make people take it less seriously.
The problem is not related to attacks or malice. It's NORMAL futex usage on the affected architectures that's broken and will throw the kernel into a loop.
/Mikael
Thomas Gleixner
Acked-by Ingo MolnarQuoted 2 lines · Adrian Bunk
The issue described in [1] is still present and unfixed (and even the fix there wasn't complete since it didn't cover SMP).
Damn, this slipped through my attention completely. Hotfix (which can be easily backported) below.
Quoted 6 lines
Thanks to Riku Voipio for noting that it is still unfixed.
cu
Adrian
-------->
Subject: futex: disable PI/robust on archs w/o valid implementation
From: Thomas Gleixner <[email protected]>
We have to disable the complete PI/robust functionality for those archs, which do not implement futex_atomic_cmpxchg_inatomic(). The code in question relies on a valid implementation and does not expect -ENOSYS, which is returned by the stub implementation in asm-generic/futex.h
Pointed out by: Mikael Pettersson, Riku Voipio and Adrian Bunk
This patch is intended for easy backporting and needs to be cleaned up further for current mainline.
--- include/asm-generic/futex.h | 2 ++ kernel/futex.c | 13 +++++++++++++ 2 files changed, 15 insertions(+)
include/asm-generic/futex.h +2 -0
@@ -55,5 +55,7 @@ futex_atomic_cmpxchg_inatomic(int __userreturn -ENOSYS ; } +#define FUTEX_ATOMIC_CMPXCHG_NOT_IMPLEMENTED +#endif #endif
kernel/futex.c +13 -0
@@ -1870,6 +1870,9 @@ asmlinkage long sys_set_robust_list(struct robust_list_head __user *head, size_t len) { +#ifdef FUTEX_ATOMIC_CMPXCHG_NOT_IMPLEMENTED +return -ENOSYS ; +#else /* * The kernel knows only one size for now: */
@@ -1879,6 +1882,7 @@ sys_set_robust_list(struct robust_list_h current->robust_list = head;return 0 ; +#endif }/**
@@ -1891,6 +1895,9 @@ asmlinkage long sys_get_robust_list(int pid, struct robust_list_head __user * __user *head_ptr, size_t __user *len_ptr) { +#ifdef FUTEX_ATOMIC_CMPXCHG_NOT_IMPLEMENTED + return -ENOSYS; +#else struct robust_list_head __user *head;unsigned long ret;
@@ -1920,6 +1927,7 @@ err_unlock:rcu_read_unlock ();return ret; +#endif }/*
@@ -2082,6 +2090,9 @@ long do_futex(u32 __user *uaddr, int op,case FUTEX_WAKE_OP : ret =futex_wake_op (uaddr, fshared, uaddr2, val, val2, val3);break ; + +#ifndef FUTEX_ATOMIC_CMPXCHG_NOT_IMPLEMENTED +case FUTEX_LOCK_PI : ret =futex_lock_pi (uaddr, fshared, val, timeout,0 );break ;
@@ -2091,6 +2102,8 @@ long do_futex(u32 __user *uaddr, int op,case FUTEX_TRYLOCK_PI : ret =futex_lock_pi (uaddr, fshared,0 , timeout,1 );break ; +#endif +default : ret = -ENOSYS ; }
Quoted 10 lines · Thomas Gleixner
Subject: futex: disable PI/robust on archs w/o valid implementation
From: Thomas Gleixner <[email protected]>We have to disable the complete PI/robust functionality for those archs, which do not implement
futex_atomic_cmpxchg_inatomic(). The code in question relies on a valid implementation and does not expect-ENOSYS, which is returned by the stub implementation inasm-generic/futex.hPointed out by: Mikael Pettersson, Riku Voipio and Adrian Bunk
FWIW, I reported it originally.
Quoted 5 lines
This patch is intended for easy backporting and needs to be cleaned up further for current mainline.
Signed-off-by Thomas Gleixner <[email protected]>Acked-by Ingo Molnar <[email protected]>
Looks good to me. Thanks.
Quoted 8 lines · Thomas Gleixner
We have to disable the complete PI/robust functionality for those archs, which do not implement
futex_atomic_cmpxchg_inatomic(). The code in question relies on a valid implementation and does not expect-ENOSYS, which is returned by the stub implementation inasm-generic/futex.hPointed out by: Mikael Pettersson, Riku Voipio and Adrian Bunk
Original credits for finding this issue belong to Lennert Buytenhek.
Quoted 5 lines
This patch is intended for easy backporting and needs to be cleaned up further for current mainline.
Signed-off-by Thomas Gleixner <[email protected]>Acked-by Ingo Molnar <[email protected]>
Looks good for me and kernel no longer deadlocks with this patch!
Quoted 26 lines · On Mon, 11 Feb 2008 14:59:34 +0100 (CET) Thomas Gleixner <[email protected]>…
Quoted 2 lines · Adrian Bunk
The issue described in [1] is still present and unfixed (and even the fix there wasn't complete since it didn't cover SMP).
Damn, this slipped through my attention completely. Hotfix (which can be easily backported) below.
Quoted 6 lines
Thanks to Riku Voipio for noting that it is still unfixed.
cu
Adrian-------->
Subject: futex: disable PI/robust on archs w/o valid implementation
From: Thomas Gleixner <[email protected]>We have to disable the complete PI/robust functionality for those archs, which do not implement
futex_atomic_cmpxchg_inatomic(). The code in question relies on a valid implementation and does not expect-ENOSYS, which is returned by the stub implementation inasm-generic/futex.h
Quoted 4 lines
Pointed out by: Mikael Pettersson, Riku Voipio and Adrian Bunk
This patch is intended for easy backporting and needs to be cleaned up further for current mainline.
So...
I queued up this version with a cc to stable under the assumption that this is the patch which should be applied to 2.6.x.y, but this version is not the one which will go into 2.6.25.
Correct?
If so: messy. The stable guys might want to wait until they see the real 2.6.25 patch and perhaps prefer to backport that version.
Quoted 5 lines · Andrew Morton
Quoted 2 lines
This patch is intended for easy backporting and needs to be cleaned up further for current mainline.
So...
Quoted 8 lines
I queued up this version with a cc to stable under the assumption that this is the patch which should be applied to 2.6.x.y, but this version is not the one which will go into 2.6.25.
Correct?
If so: messy. The stable guys might want to wait until they see the real 2.6.25 patch and perhaps prefer to backport that version.
Yup. I worked out a sane solution, which allows runtime detection. The compile time solution is not perfect, as there is already arch code which checks cpu features on runtime.
Patches follow in separate mail.
Thanks,
tglx
PATCH 1/2 futex: fix init order
When the futex init code fails to initialize the futex pseudo file system it returns early without initializing the hash queues. Should the boot succeed then a futex syscall which tries to enqueue a waiter on the hashqueue will crash due to the unitilialized plist heads.
Initialize the hash queues before the filesystem.
--- kernel/futex.c | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-)
kernel/futex.c +7 -5
@@ -2145,8 +2145,14 @@ static struct file_system_type futex_fs_static int __init init (void ) { -int i =register_filesystem (&futex_fs_type); +int i; +for (i =0 ; i <ARRAY_SIZE (futex_queues); i++) { +plist_head_init (&futex_queues[i].chain, &futex_queues[i].lock); +spin_lock_init (&futex_queues[i].lock); + } + + i =register_filesystem (&futex_fs_type);if (i)return i;
@@ -2156,10 +2162,6 @@ static int __init init(void)return PTR_ERR (futex_mnt); } -for (i =0 ; i <ARRAY_SIZE (futex_queues); i++) { -plist_head_init (&futex_queues[i].chain, &futex_queues[i].lock); -spin_lock_init (&futex_queues[i].lock); - }return 0 ; }__initcall (init);
PATCH 2/2 futex: runtime enable pi and robust functionality
In reply to Thomas GleixnerNot all architectures implement futex_atomic_cmpxchg_inatomic(). The default implementation returns -ENOSYS, which is currently not handled inside of the futex guts.
Futex PI calls and robust list exits with a held futex result in an endless loop in the futex code on architectures which have no support.
Fixing up every place where futex_atomic_cmpxchg_inatomic() is called would add a fair amount of extra if/else constructs to the already complex code. It is also not possible to disable the robust feature before user space tries to register robust lists.
Compile time disabling is not a good idea either, as there are already architectures with runtime detection of futex_atomic_cmpxchg_inatomic support.
Detect the functionality at runtime instead by calling cmpxchg_futex_value_locked() with a NULL pointer from the futex initialization code. This is guaranteed to fail, but the call of futex_atomic_cmpxchg_inatomic() happens with pagefaults disabled.
On architectures, which use the asm-generic implementation or have a runtime CPU feature detection, a -ENOSYS return value disables the PI/robust features.
On architectures with a working implementation the call returns -EFAULT and the PI/robust features are enabled.
The relevant syscalls return -ENOSYS and the robust list exit code is blocked, when the detection fails.
Fixes http://lkml.org/lkml/2008/2/11/149
Originally reported by: Lennart Buytenhek
--- include/linux/futex.h | 1 + kernel/futex.c | 38 ++++++++++++++++++++++++++++++++++---- kernel/futex_compat.c | 9 +++++++++ 3 files changed, 44 insertions(+), 4 deletions(-)
include/linux/futex.h +1 -0
@@ -167,6 +167,7 @@ union futex_key {#ifdef CONFIG_FUTEX extern void exit_robust_list (struct task_struct *curr);extern void exit_pi_state_list (struct task_struct *curr); +extern int futex_cmpxchg_enabled;#else static inline void exit_robust_list (struct task_struct *curr) {
kernel/futex.c +34 -4
@@ -60,6 +60,8 @@#include "rtmutex_common.h" +int __read_mostly futex_cmpxchg_enabled; +#define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)/*
@@ -469,6 +471,8 @@ void exit_pi_state_list(struct task_strustruct futex_hash_bucket *hb;union futex_key key; +if (!futex_cmpxchg_enabled) +return ;/* * We are a ZOMBIE and nobody can enqueue itself on * pi_state_list anymore, but we have to be careful
@@ -1870,6 +1874,8 @@ asmlinkage long sys_set_robust_list(struct robust_list_head __user *head, size_t len) { +if (!futex_cmpxchg_enabled) +return -ENOSYS ;/* * The kernel knows only one size for now: */
@@ -1894,6 +1900,9 @@ sys_get_robust_list(int pid, struct robustruct robust_list_head __user *head;unsigned long ret; +if (!futex_cmpxchg_enabled) +return -ENOSYS ; +if (!pid) head = current->robust_list;else {
@@ -1997,6 +2006,9 @@ void exit_robust_list(struct task_structunsigned long futex_offset;int rc; +if (!futex_cmpxchg_enabled) +return ; +/* * Fetch the list head (which was registered earlier, via * sys_set_robust_list()):
@@ -2051,7 +2063,7 @@ void exit_robust_list(struct task_structlong do_futex (u32 __user *uaddr,int op,u32 val,ktime_t *timeout,u32 __user *uaddr2,u32 val2,u32 val3) { -int ret; +int ret = -ENOSYS ;int cmd = op &FUTEX_CMD_MASK ;struct rw_semaphore *fshared =NULL ;
@@ -2083,13 +2095,16 @@ long do_futex(u32 __user *uaddr, int op, ret =futex_wake_op (uaddr, fshared, uaddr2, val, val2, val3);break ;case FUTEX_LOCK_PI : - ret =futex_lock_pi (uaddr, fshared, val, timeout,0 ); +if (futex_cmpxchg_enabled) + ret =futex_lock_pi (uaddr, fshared, val, timeout,0 );break ;case FUTEX_UNLOCK_PI : - ret =futex_unlock_pi (uaddr, fshared); +if (futex_cmpxchg_enabled) + ret =futex_unlock_pi (uaddr, fshared);break ;case FUTEX_TRYLOCK_PI : - ret =futex_lock_pi (uaddr, fshared,0 , timeout,1 ); +if (futex_cmpxchg_enabled) + ret =futex_lock_pi (uaddr, fshared,0 , timeout,1 );break ;default : ret = -ENOSYS ;
@@ -2145,8 +2160,23 @@ static struct file_system_type futex_fs_static int __init init (void ) { +u32 curval;int i; +/* +* This will fail and we want it. Some arch implementations do +* runtime detection of the futex_atomic_cmpxchg_inatomic() +* functionality. We want to know that before we call in any +* of the complex code paths. Also we want to prevent +* registration of robust lists in that case. NULL is +* guaranteed to fault and we get -EFAULT on functional +* implementation, the non functional ones will return +* -ENOSYS. +*/ + curval =cmpxchg_futex_value_locked (NULL ,0 ,0 ); +if (curval == -EFAULT ) + futex_cmpxchg_enabled =1 ; +for (i =0 ; i <ARRAY_SIZE (futex_queues); i++) {plist_head_init (&futex_queues[i].chain, &futex_queues[i].lock);spin_lock_init (&futex_queues[i].lock);
kernel/futex_compat.c +9 -0
@@ -54,6 +54,9 @@ void compat_exit_robust_list(struct taskcompat_long_t futex_offset;int rc; +if (!futex_cmpxchg_enabled) +return ; +/* * Fetch the list head (which was registered earlier, via * sys_set_robust_list()):
@@ -115,6 +118,9 @@ asmlinkage long compat_sys_set_robust_list(struct compat_robust_list_head __user *head, compat_size_t len) { +if (!futex_cmpxchg_enabled) +return -ENOSYS ; +if (unlikely (len !=sizeof (*head)))return -EINVAL ;
@@ -130,6 +136,9 @@ compat_sys_get_robust_list(int pid, compstruct compat_robust_list_head __user *head;unsigned long ret; +if (!futex_cmpxchg_enabled) +return -ENOSYS ; +if (!pid) head = current->compat_robust_list;else {