futex local DoS on most architectures

futex local DoS on most architectures

[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

[1] http://lkml.org/lkml/2007/8/1/474

Re: futex local DoS on most architectures

[Mikael Pettersson]

Adrian Bunk writes:
 > 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
 > 
 > [1] http://lkml.org/lkml/2007/8/1/474

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

Re: futex local DoS on most architectures

[Thomas Gleixner]

On Mon, 11 Feb 2008, Adrian Bunk wrote:

> 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.
 
> Thanks to Riku Voipio for noting that it is still unfixed.
> 
> cu
> Adrian
> 
> [1] http://lkml.org/lkml/2007/8/1/474

-------->

Subject: futex: disable PI/robust on archs w/o valid implementation
From: Thomas Gleixner <tglx@linutronix.de>

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.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Ingo Molnar <mingo@elte.hu>
---
 include/asm-generic/futex.h |    2 ++
 kernel/futex.c              |   13 +++++++++++++
 2 files changed, 15 insertions(+)

Index: linux-2.6/include/asm-generic/futex.h
===================================================================
--- linux-2.6.orig/include/asm-generic/futex.h
+++ linux-2.6/include/asm-generic/futex.h
@@ -55,5 +55,7 @@ futex_atomic_cmpxchg_inatomic(int __user
 	return -ENOSYS;
 }
 
+#define FUTEX_ATOMIC_CMPXCHG_NOT_IMPLEMENTED
+
 #endif
 #endif
Index: linux-2.6/kernel/futex.c
===================================================================
--- linux-2.6.orig/kernel/futex.c
+++ linux-2.6/kernel/futex.c
@@ -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;
 	}

Re: futex local DoS on most architectures

[Lennert Buytenhek]

On Mon, Feb 11, 2008 at 02:59:34PM +0100, Thomas Gleixner wrote:

> Subject: futex: disable PI/robust on archs w/o valid implementation
> From: Thomas Gleixner <tglx@linutronix.de>
> 
> 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

FWIW, I reported it originally.


> This patch is intended for easy backporting and needs to be cleaned up
> further for current mainline.
> 
> Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
> Acked-by: Ingo Molnar <mingo@elte.hu>

Looks good to me.  Thanks.

Re: futex local DoS on most architectures

[Riku Voipio]

Thomas Gleixner wrote:
> 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
>   
Original credits for finding this issue belong to Lennert Buytenhek.
> This patch is intended for easy backporting and needs to be cleaned up
> further for current mainline.
>
> Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
> Acked-by: Ingo Molnar <mingo@elte.hu>
Looks good for me and kernel no longer deadlocks with this patch!

Re: futex local DoS on most architectures

[Andrew Morton]

On Mon, 11 Feb 2008 14:59:34 +0100 (CET)
Thomas Gleixner <tglx@linutronix.de> wrote:

> On Mon, 11 Feb 2008, Adrian Bunk wrote:
> 
> > 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.
>  
> > Thanks to Riku Voipio for noting that it is still unfixed.
> > 
> > cu
> > Adrian
> > 
> > [1] http://lkml.org/lkml/2007/8/1/474
> 
> -------->
> 
> Subject: futex: disable PI/robust on archs w/o valid implementation
> From: Thomas Gleixner <tglx@linutronix.de>
> 
> 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.

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.

Re: futex local DoS on most architectures

[Thomas Gleixner]

On Thu, 14 Feb 2008, Andrew Morton wrote:
> > 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.

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

[Thomas Gleixner]

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.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Ingo Molnar <mingo@elte.hu>

---
 kernel/futex.c |   12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

Index: linux-2.6/kernel/futex.c
===================================================================
--- linux-2.6.orig/kernel/futex.c
+++ linux-2.6/kernel/futex.c
@@ -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

[Thomas Gleixner]

Not 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

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Acked-by: Ingo Molnar <mingo@elte.hu>
Cc: stable@kernel.org

---
 include/linux/futex.h |    1 +
 kernel/futex.c        |   38 ++++++++++++++++++++++++++++++++++----
 kernel/futex_compat.c |    9 +++++++++
 3 files changed, 44 insertions(+), 4 deletions(-)

Index: linux-2.6/include/linux/futex.h
===================================================================
--- linux-2.6.orig/include/linux/futex.h
+++ linux-2.6/include/linux/futex.h
@@ -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)
 {
Index: linux-2.6/kernel/futex.c
===================================================================
--- linux-2.6.orig/kernel/futex.c
+++ linux-2.6/kernel/futex.c
@@ -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_stru
 	struct 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 robu
 	struct 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_struct
 	unsigned 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_struct
 long 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);
Index: linux-2.6/kernel/futex_compat.c
===================================================================
--- linux-2.6.orig/kernel/futex_compat.c
+++ linux-2.6/kernel/futex_compat.c
@@ -54,6 +54,9 @@ void compat_exit_robust_list(struct task
 	compat_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, comp
 	struct compat_robust_list_head __user *head;
 	unsigned long ret;
 
+	if (!futex_cmpxchg_enabled)
+		return -ENOSYS;
+
 	if (!pid)
 		head = current->compat_robust_list;
 	else {