Skip to contentSkip to conversation

futex local DoS on most architectures

PATCH New Adrian Bunk 6 participants 9 messages Feb 11, 2008 – Feb 15, 2008

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

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

#1 lore raw
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

[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

Acked-by Ingo Molnar
#2 lore raw
In reply to Adrian Bunk
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

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

-------->

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
Index: 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
kernel/futex.c +13 -0
Index: 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;
 	}
#3 lore raw
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 in asm-generic/futex.h

Pointed 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.

Looks good to me. Thanks.

#4 lore raw
In reply to Thomas Gleixner
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 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.

Quoted 5 lines

This patch is intended for easy backporting and needs to be cleaned up further for current mainline.

Looks good for me and kernel no longer deadlocks with this patch!

#5 lore raw
In reply to Thomas Gleixner
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

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

-------->

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

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.

#6 lore raw
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

#7 lore raw

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
Index: 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);
#8 lore raw

PATCH 2/2 futex: runtime enable pi and robust functionality

In reply to 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

---
 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
Index: 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)
 {
kernel/futex.c +34 -4
Index: 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);
kernel/futex_compat.c +9 -0
Index: 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 {