Create a test for the robust list mechanism. Test the following uAPI operations:

- Creating a robust mutex where the lock waiter is wake by the kernel when the lock owner died - Setting a robust list to the current task - Getting a robust list from the current task - Getting a robust list from another task - Using the list_op_pending field from robust_list_head struct to test robustness when the lock owner dies before completing the locking - Setting a invalid size for syscall argument `len` - Adding multiple elements to a robust list wait waiting for each of them - Creating a circular list and checking that the kernel does not get stuck in an infinity loop

This is the expected output:

TAP version 13 1..7 ok 1 test_robustness ok 2 test_set_robust_list_invalid_size ok 3 test_get_robust_list_self ok 4 test_get_robust_list_child ok 5 test_set_list_op_pending ok 6 test_robust_list_multiple_elements ok 7 test_circular_list # Totals: pass:7 fail:0 xfail:0 xpass:0 skip:0 error:0

Signed-off-by: André Almeida andrealmeid@igalia.com --- .../testing/selftests/futex/functional/.gitignore | 1 + tools/testing/selftests/futex/functional/Makefile | 3 +- .../selftests/futex/functional/robust_list.c | 554 +++++++++++++++++++++ 3 files changed, 557 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/futex/functional/.gitignore b/tools/testing/selftests/futex/functional/.gitignore index 7b24ae89594a9db211d4b8469ebcef8d1f7012d8..7f447ebfbc62bbad9add0dc86a75abcdb8a4d9a7 100644 --- a/tools/testing/selftests/futex/functional/.gitignore +++ b/tools/testing/selftests/futex/functional/.gitignore @@ -11,3 +11,4 @@ futex_wait_timeout futex_wait_uninitialized_heap futex_wait_wouldblock futex_waitv +robust_list diff --git a/tools/testing/selftests/futex/functional/Makefile b/tools/testing/selftests/futex/functional/Makefile index 8cfb87f7f7c5059c82f1e6290c076d3f13f5ea41..e6fa66e622dee4de74c31c8b9b486ca01de35737 100644 --- a/tools/testing/selftests/futex/functional/Makefile +++ b/tools/testing/selftests/futex/functional/Makefile @@ -20,7 +20,8 @@ TEST_GEN_PROGS := \ futex_priv_hash \ futex_numa_mpol \ futex_waitv \ - futex_numa + futex_numa \ + robust_list

TEST_PROGS := run.sh

diff --git a/tools/testing/selftests/futex/functional/robust_list.c b/tools/testing/selftests/futex/functional/robust_list.c new file mode 100644 index 0000000000000000000000000000000000000000..42690b2440fd29a9b12c46f67f9645ccc93d1147 --- /dev/null +++ b/tools/testing/selftests/futex/functional/robust_list.c @@ -0,0 +1,554 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Copyright (C) 2024 Igalia S.L. + * + * Robust list test by André Almeida andrealmeid@igalia.com + * + * The robust list uAPI allows userspace to create "robust" locks, in the sense + * that if the lock holder thread dies, the remaining threads that are waiting + * for the lock won't block forever, waiting for a lock that will never be + * released. + * + * This is achieve by userspace setting a list where a thread can enter all the + * locks (futexes) that it is holding. The robust list is a linked list, and + * userspace register the start of the list with the syscall set_robust_list(). + * If such thread eventually dies, the kernel will walk this list, waking up one + * thread waiting for each futex and marking the futex word with the flag + * FUTEX_OWNER_DIED. + * + * See also + * man set_robust_list + * Documententation/locking/robust-futex-ABI.rst + * Documententation/locking/robust-futexes.rst + */ + +#define _GNU_SOURCE + +#include "futextest.h" +#include "logging.h" + +#include <errno.h> +#include <pthread.h> +#include <signal.h> +#include <stdatomic.h> +#include <stdbool.h> +#include <stddef.h> +#include <sys/mman.h> +#include <sys/wait.h> + +#define STACK_SIZE (1024 * 1024) + +#define FUTEX_TIMEOUT 3 + +static pthread_barrier_t barrier, barrier2; + +int set_robust_list(struct robust_list_head *head, size_t len) +{ + return syscall(SYS_set_robust_list, head, len); +} + +int get_robust_list(int pid, struct robust_list_head **head, size_t *len_ptr) +{ + return syscall(SYS_get_robust_list, pid, head, len_ptr); +} + +/* + * Basic lock struct, contains just the futex word and the robust list element + * Real implementations have also a *prev to easily walk in the list + */ +struct lock_struct { + _Atomic(unsigned int) futex; + struct robust_list list; +}; + +/* + * Helper function to spawn a child thread. Returns -1 on error, pid on success + */ +static int create_child(int (*fn)(void *arg), void *arg) +{ + char *stack; + pid_t pid; + + stack = mmap(NULL, STACK_SIZE, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK, -1, 0); + if (stack == MAP_FAILED) + return -1; + + stack += STACK_SIZE; + + pid = clone(fn, stack, CLONE_VM | SIGCHLD, arg); + + if (pid == -1) + return -1; + + return pid; +} + +/* + * Helper function to prepare and register a robust list + */ +static int set_list(struct robust_list_head *head) +{ + int ret; + + ret = set_robust_list(head, sizeof(struct robust_list_head)); + if (ret) + return ret; + + head->futex_offset = (size_t) offsetof(struct lock_struct, futex) - + (size_t) offsetof(struct lock_struct, list); + head->list.next = &head->list; + head->list_op_pending = NULL; + + return 0; +} + +/* + * A basic (and incomplete) mutex lock function with robustness + */ +static int mutex_lock(struct lock_struct *lock, struct robust_list_head *head, bool error_inject) +{ + _Atomic(unsigned int) *futex = &lock->futex; + unsigned int zero = 0; + int ret = -1; + pid_t tid = gettid(); + + /* + * Set list_op_pending before starting the lock, so the kernel can catch + * the case where the thread died during the lock operation + */ + head->list_op_pending = &lock->list; + + if (atomic_compare_exchange_strong(futex, &zero, tid)) { + /* + * We took the lock, insert it in the robust list + */ + struct robust_list *list = &head->list; + + /* Error injection to test list_op_pending */ + if (error_inject) + return 0; + + while (list->next != &head->list) + list = list->next; + + list->next = &lock->list; + lock->list.next = &head->list; + + ret = 0; + } else { + /* + * We didn't take the lock, wait until the owner wakes (or dies) + */ + struct timespec to; + + to.tv_sec = FUTEX_TIMEOUT; + to.tv_nsec = 0; + + tid = atomic_load(futex); + /* Kernel ignores futexes without the waiters flag */ + tid |= FUTEX_WAITERS; + atomic_store(futex, tid); + + ret = futex_wait((futex_t *) futex, tid, &to, 0); + + /* + * A real mutex_lock() implementation would loop here to finally + * take the lock. We don't care about that, so we stop here. + */ + } + + head->list_op_pending = NULL; + + return ret; +} + +/* + * This child thread will succeed taking the lock, and then will exit holding it + */ +static int child_fn_lock(void *arg) +{ + struct lock_struct *lock = (struct lock_struct *) arg; + struct robust_list_head head; + int ret; + + ret = set_list(&head); + if (ret) + ksft_test_result_fail("set_robust_list error\n"); + + ret = mutex_lock(lock, &head, false); + if (ret) + ksft_test_result_fail("mutex_lock error\n"); + + pthread_barrier_wait(&barrier); + + /* + * There's a race here: the parent thread needs to be inside + * futex_wait() before the child thread dies, otherwise it will miss the + * wakeup from handle_futex_death() that this child will emit. We wait a + * little bit just to make sure that this happens. + */ + sleep(1); + + return 0; +} + +/* + * Spawns a child thread that will set a robust list, take the lock, register it + * in the robust list and die. The parent thread will wait on this futex, and + * should be waken up when the child exits. + */ +static void test_robustness(void) +{ + struct lock_struct lock = { .futex = 0 }; + struct robust_list_head head; + _Atomic(unsigned int) *futex = &lock.futex; + int ret; + + ret = set_list(&head); + ASSERT_EQ(ret, 0); + + /* + * Lets use a barrier to ensure that the child thread takes the lock + * before the parent + */ + ret = pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + + ret = create_child(&child_fn_lock, &lock); + ASSERT_NE(ret, -1); + + pthread_barrier_wait(&barrier); + ret = mutex_lock(&lock, &head, false); + + /* + * futex_wait() should return 0 and the futex word should be marked with + * FUTEX_OWNER_DIED + */ + ASSERT_EQ(ret, 0); + if (ret != 0) + printf("futex wait returned %d", errno); + + ASSERT_TRUE(*futex | FUTEX_OWNER_DIED); + + wait(NULL); + pthread_barrier_destroy(&barrier); + + ksft_test_result_pass("%s\n", __func__); +} + +/* + * The only valid value for len is sizeof(*head) + */ +static void test_set_robust_list_invalid_size(void) +{ + struct robust_list_head head; + size_t head_size = sizeof(struct robust_list_head); + int ret; + + ret = set_robust_list(&head, head_size); + ASSERT_EQ(ret, 0); + + ret = set_robust_list(&head, head_size * 2); + ASSERT_EQ(ret, -1); + ASSERT_EQ(errno, EINVAL); + + ret = set_robust_list(&head, head_size - 1); + ASSERT_EQ(ret, -1); + ASSERT_EQ(errno, EINVAL); + + ret = set_robust_list(&head, 0); + ASSERT_EQ(ret, -1); + ASSERT_EQ(errno, EINVAL); + + ksft_test_result_pass("%s\n", __func__); +} + +/* + * Test get_robust_list with pid = 0, getting the list of the running thread + */ +static void test_get_robust_list_self(void) +{ + struct robust_list_head head, head2, *get_head; + size_t head_size = sizeof(struct robust_list_head), len_ptr; + int ret; + + ret = set_robust_list(&head, head_size); + ASSERT_EQ(ret, 0); + + ret = get_robust_list(0, &get_head, &len_ptr); + ASSERT_EQ(ret, 0); + ASSERT_EQ(get_head, &head); + ASSERT_EQ(head_size, len_ptr); + + ret = set_robust_list(&head2, head_size); + ASSERT_EQ(ret, 0); + + ret = get_robust_list(0, &get_head, &len_ptr); + ASSERT_EQ(ret, 0); + ASSERT_EQ(get_head, &head2); + ASSERT_EQ(head_size, len_ptr); + + ksft_test_result_pass("%s\n", __func__); +} + +static int child_list(void *arg) +{ + struct robust_list_head *head = (struct robust_list_head *) arg; + int ret; + + ret = set_robust_list(head, sizeof(struct robust_list_head)); + if (ret) + ksft_test_result_fail("set_robust_list error\n"); + + pthread_barrier_wait(&barrier); + pthread_barrier_wait(&barrier2); + + return 0; +} + +/* + * Test get_robust_list from another thread. We use two barriers here to ensure + * that: + * 1) the child thread set the list before we try to get it from the + * parent + * 2) the child thread still alive when we try to get the list from it + */ +static void test_get_robust_list_child(void) +{ + pid_t tid; + int ret; + struct robust_list_head head, *get_head; + size_t len_ptr; + + ret = pthread_barrier_init(&barrier, NULL, 2); + ret = pthread_barrier_init(&barrier2, NULL, 2); + ASSERT_EQ(ret, 0); + + tid = create_child(&child_list, &head); + ASSERT_NE(tid, -1); + + pthread_barrier_wait(&barrier); + + ret = get_robust_list(tid, &get_head, &len_ptr); + ASSERT_EQ(ret, 0); + ASSERT_EQ(&head, get_head); + + pthread_barrier_wait(&barrier2); + + wait(NULL); + pthread_barrier_destroy(&barrier); + pthread_barrier_destroy(&barrier2); + + ksft_test_result_pass("%s\n", __func__); +} + +static int child_fn_lock_with_error(void *arg) +{ + struct lock_struct *lock = (struct lock_struct *) arg; + struct robust_list_head head; + int ret; + + ret = set_list(&head); + if (ret) + ksft_test_result_fail("set_robust_list error\n"); + + ret = mutex_lock(lock, &head, true); + if (ret) + ksft_test_result_fail("mutex_lock error\n"); + + pthread_barrier_wait(&barrier); + + sleep(1); + + return 0; +} + +/* + * Same as robustness test, but inject an error where the mutex_lock() exits + * earlier, just after setting list_op_pending and taking the lock, to test the + * list_op_pending mechanism + */ +static void test_set_list_op_pending(void) +{ + struct lock_struct lock = { .futex = 0 }; + struct robust_list_head head; + _Atomic(unsigned int) *futex = &lock.futex; + int ret; + + ret = set_list(&head); + ASSERT_EQ(ret, 0); + + ret = pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + + ret = create_child(&child_fn_lock_with_error, &lock); + ASSERT_NE(ret, -1); + + pthread_barrier_wait(&barrier); + ret = mutex_lock(&lock, &head, false); + + ASSERT_EQ(ret, 0); + if (ret != 0) + printf("futex wait returned %d", errno); + + ASSERT_TRUE(*futex | FUTEX_OWNER_DIED); + + wait(NULL); + pthread_barrier_destroy(&barrier); + + ksft_test_result_pass("%s\n", __func__); +} + +#define CHILD_NR 10 + +static int child_lock_holder(void *arg) +{ + struct lock_struct *locks = (struct lock_struct *) arg; + struct robust_list_head head; + int i; + + set_list(&head); + + for (i = 0; i < CHILD_NR; i++) { + locks[i].futex = 0; + mutex_lock(&locks[i], &head, false); + } + + pthread_barrier_wait(&barrier); + pthread_barrier_wait(&barrier2); + + sleep(1); + return 0; +} + +static int child_wait_lock(void *arg) +{ + struct lock_struct *lock = (struct lock_struct *) arg; + struct robust_list_head head; + int ret; + + pthread_barrier_wait(&barrier2); + ret = mutex_lock(lock, &head, false); + + if (ret) + ksft_test_result_fail("mutex_lock error\n"); + + if (!(lock->futex | FUTEX_OWNER_DIED)) + ksft_test_result_fail("futex not marked with FUTEX_OWNER_DIED\n"); + + return 0; +} + +/* + * Test a robust list of more than one element. All the waiters should wake when + * the holder dies + */ +static void test_robust_list_multiple_elements(void) +{ + struct lock_struct locks[CHILD_NR]; + int i, ret; + + ret = pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + ret = pthread_barrier_init(&barrier2, NULL, CHILD_NR + 1); + ASSERT_EQ(ret, 0); + + create_child(&child_lock_holder, &locks); + + /* Wait until the locker thread takes the look */ + pthread_barrier_wait(&barrier); + + for (i = 0; i < CHILD_NR; i++) + create_child(&child_wait_lock, &locks[i]); + + /* Wait for all children to return */ + while (wait(NULL) > 0); + + pthread_barrier_destroy(&barrier); + pthread_barrier_destroy(&barrier2); + + ksft_test_result_pass("%s\n", __func__); +} + +static int child_circular_list(void *arg) +{ + static struct robust_list_head head; + struct lock_struct a, b, c; + int ret; + + ret = set_list(&head); + if (ret) + ksft_test_result_fail("set_list error\n"); + + head.list.next = &a.list; + + /* + * The last element should point to head list, but we short circuit it + */ + a.list.next = &b.list; + b.list.next = &c.list; + c.list.next = &a.list; + + return 0; +} + +/* + * Create a circular robust list. The kernel should be able to destroy the list + * while processing it so it won't be trapped in an infinite loop while handling + * a process exit + */ +static void test_circular_list(void) +{ + create_child(child_circular_list, NULL); + + wait(NULL); + + ksft_test_result_pass("%s\n", __func__); +} + +void usage(char *prog) +{ + printf("Usage: %s\n", prog); + printf(" -c Use color\n"); + printf(" -h Display this help message\n"); + printf(" -v L Verbosity level: %d=QUIET %d=CRITICAL %d=INFO\n", + VQUIET, VCRITICAL, VINFO); +} + +int main(int argc, char *argv[]) +{ + int c; + + while ((c = getopt(argc, argv, "cht:v:")) != -1) { + switch (c) { + case 'c': + log_color(1); + break; + case 'h': + usage(basename(argv[0])); + exit(0); + case 'v': + log_verbosity(atoi(optarg)); + break; + default: + usage(basename(argv[0])); + exit(1); + } + } + + ksft_print_header(); + ksft_set_plan(7); + + test_robustness(); + + test_set_robust_list_invalid_size(); + test_get_robust_list_self(); + test_get_robust_list_child(); + test_set_list_op_pending(); + test_robust_list_multiple_elements(); + test_circular_list(); + + ksft_print_cnts(); + return 0; +}

Create a new robust_list() syscall. The current syscall can't be expanded to cover the following use case, so a new one is needed. This new syscall allows users to set multiple robust lists per process and to have either 32bit or 64bit pointers in the list.

* Interface

This is the proposed interface:

long set_robust_list2(void *head, int index, unsigned int flags)

`head` is the head of the userspace struct robust_list_head, just as old set_robust_list(). It needs to be a void pointer since it can point to a normal robust_list_head or a compat_robust_list_head.

`flags` can be used for defining the list type:

enum robust_list_type { ROBUST_LIST_32BIT, ROBUST_LIST_64BIT, };

`index` is the index in the internal robust_list's linked list (the naming starts to get confusing, I reckon). If `index == -1`, that means that user wants to set a new robust_list, and the kernel will append it in the end of the list, assign a new index and return this index to the user. If `index >= 0`, that means that user wants to re-set `*head` of an already existing list (similarly to what happens when you call set_robust_list() twice with different `*head`).

If `index` is out of range, or it points to a non-existing robust_list, or if the internal list is full, an error is returned.

Unaligned `head` addresses are refused by the kernel with -EINVAL.

User cannot remove lists.

* Implementation

The old syscall's set/get_robust_list() are converted to use the linked list as well. When using only the old syscalls user shouldn't any difference as the internal code will handle the linked list insertion as usual. When mixing old and new interfaces users should be aware that one of the elements of the list was created by another syscall and they should have special care handling this element index.

On exit, the linked list is parsed and all robust lists regardless of which interface it was used to create them are handled.

Signed-off-by: André Almeida andrealmeid@igalia.com --- include/linux/futex.h | 5 +- include/linux/sched.h | 5 +- include/uapi/asm-generic/unistd.h | 2 + include/uapi/linux/futex.h | 24 +++++++++ kernel/futex/core.c | 111 ++++++++++++++++++++++++++++++-------- kernel/futex/futex.h | 5 ++ kernel/futex/syscalls.c | 81 ++++++++++++++++++++++++++-- 7 files changed, 204 insertions(+), 29 deletions(-)

diff --git a/include/linux/futex.h b/include/linux/futex.h index cd7c5d12c846566c56f3f3ea74b95e437a6e8193..7721629926535c775bd7b05b5283a3d0b51262d6 100644 --- a/include/linux/futex.h +++ b/include/linux/futex.h @@ -75,10 +75,11 @@ enum {

static inline void futex_init_task(struct task_struct *tsk) { - tsk->robust_list = NULL; + tsk->robust_list_index = -1; #ifdef CONFIG_COMPAT - tsk->compat_robust_list = NULL; + tsk->compat_robust_list_index = -1; #endif + INIT_LIST_HEAD(&tsk->robust_list2); INIT_LIST_HEAD(&tsk->pi_state_list); tsk->pi_state_cache = NULL; tsk->futex_state = FUTEX_STATE_OK; diff --git a/include/linux/sched.h b/include/linux/sched.h index 51e5d05a9fcd407dcd53b7b7cb8c59783660a826..a37c55cf0a4d942ec1fbedb8bcd4be5a3ebb20bb 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1322,10 +1322,11 @@ struct task_struct { u32 rmid; #endif #ifdef CONFIG_FUTEX - struct robust_list_head __user *robust_list; + int robust_list_index; #ifdef CONFIG_COMPAT - struct robust_list_head32 __user *compat_robust_list; + int compat_robust_list_index; #endif + struct list_head robust_list2; struct list_head pi_state_list; struct futex_pi_state *pi_state_cache; struct mutex futex_exit_mutex; diff --git a/include/uapi/asm-generic/unistd.h b/include/uapi/asm-generic/unistd.h index 2892a45023af6d3eb941623d4fed04841ab07e02..ebe68c2c88eb5390dda184ce9268a8d3a606c9e5 100644 --- a/include/uapi/asm-generic/unistd.h +++ b/include/uapi/asm-generic/unistd.h @@ -852,6 +852,8 @@ __SYSCALL(__NR_removexattrat, sys_removexattrat) #define __NR_open_tree_attr 467 __SYSCALL(__NR_open_tree_attr, sys_open_tree_attr)

+#define __NR_set_robust_list2 467 + #undef __NR_syscalls #define __NR_syscalls 468

diff --git a/include/uapi/linux/futex.h b/include/uapi/linux/futex.h index 7e2744ec89336a260e89883e95222eda199eeb7f..cbd321eca03afb6bdcf47e9534761d82f9de7e43 100644 --- a/include/uapi/linux/futex.h +++ b/include/uapi/linux/futex.h @@ -153,6 +153,30 @@ struct robust_list_head { struct robust_list __user *list_op_pending; };

+#define ROBUST_LISTS_PER_TASK 10 + +enum robust_list2_type { + ROBUST_LIST_32BIT, + ROBUST_LIST_64BIT, +}; + +#define ROBUST_LIST_TYPE_MASK (ROBUST_LIST_32BIT | ROBUST_LIST_64BIT) + +/* + * This is an entry of a linked list of robust lists. + * + * @head: can point to a 64bit list or a 32bit list + * @list_type: determine the size of the futex pointers in the list + * @index: the index of this entry in the list + * @list: linked list element + */ +struct robust_list2_entry { + void __user *head; + enum robust_list2_type list_type; + unsigned int index; + struct list_head list; +}; + /* * Are there any waiters for this robust futex: */ diff --git a/kernel/futex/core.c b/kernel/futex/core.c index 8640770aadc611b7341a3abb41bdb740e6394479..49b3bc592948a811f995017027f33ad8f285531f 100644 --- a/kernel/futex/core.c +++ b/kernel/futex/core.c @@ -1151,9 +1151,9 @@ static inline int fetch_robust_entry(struct robust_list __user **entry, * * We silently return on any sign of list-walking problem. */ -static void exit_robust_list64(struct task_struct *curr) +static void exit_robust_list64(struct task_struct *curr, + struct robust_list_head __user *head) { - struct robust_list_head __user *head = curr->robust_list; struct robust_list __user *entry, *next_entry, *pending; unsigned int limit = ROBUST_LIST_LIMIT, pi, pip; unsigned int next_pi; @@ -1213,7 +1213,8 @@ static void exit_robust_list64(struct task_struct *curr) } } #else -static void exit_robust_list64(struct task_struct *curr) +static void exit_robust_list64(struct task_struct *curr, + struct robust_list_head __user *head) { pr_warn("32bit kernel should not allow ROBUST_LIST_64BIT"); } @@ -1250,9 +1251,9 @@ fetch_robust_entry32(u32 *uentry, struct robust_list __user **entry, * * We silently return on any sign of list-walking problem. */ -static void exit_robust_list32(struct task_struct *curr) +static void exit_robust_list32(struct task_struct *curr, + struct robust_list_head32 __user *head) { - struct robust_list_head32 __user *head = curr->compat_robust_list; struct robust_list __user *entry, *next_entry, *pending; unsigned int limit = ROBUST_LIST_LIMIT, pi, pip; unsigned int next_pi; @@ -1318,6 +1319,70 @@ static void exit_robust_list32(struct task_struct *curr) } }

+long do_set_robust_list2(struct robust_list_head __user *head, + int index, unsigned int type) +{ + struct list_head *list2 = &current->robust_list2; + struct robust_list2_entry *prev, *new = NULL; + + if (index == -1) { + if (list_empty(list2)) { + index = 0; + } else { + prev = list_last_entry(list2, struct robust_list2_entry, list); + index = prev->index + 1; + } + + if (index >= ROBUST_LISTS_PER_TASK) + return -EINVAL; + + new = kmalloc(sizeof(struct robust_list2_entry), GFP_KERNEL); + if (!new) + return -ENOMEM; + + list_add_tail(&new->list, list2); + new->index = index; + + } else if (index >= 0) { + struct robust_list2_entry *curr; + + if (list_empty(list2)) + return -ENOENT; + + list_for_each_entry(curr, list2, list) { + if (index == curr->index) { + new = curr; + break; + } + } + + if (!new) + return -ENOENT; + } + + BUG_ON(!new); + new->head = head; + new->list_type = type; + + return index; +} + +struct robust_list_head __user *get_robust_list2(int index, struct task_struct *task) +{ + struct list_head *list2 = &task->robust_list2; + struct robust_list2_entry *curr; + + if (list_empty(list2) || index == -1) + return NULL; + + list_for_each_entry(curr, list2, list) { + if (index == curr->index) + return curr->head; + } + + return NULL; +} + #ifdef CONFIG_FUTEX_PI

/* @@ -1411,24 +1476,28 @@ static inline void exit_pi_state_list(struct task_struct *curr) { }

static void futex_cleanup(struct task_struct *tsk) { -#ifdef CONFIG_64BIT - if (unlikely(tsk->robust_list)) { - exit_robust_list64(tsk); - tsk->robust_list = NULL; - } -#else - if (unlikely(tsk->robust_list)) { - exit_robust_list32(tsk); - tsk->robust_list = NULL; - } -#endif + struct robust_list2_entry *curr, *n; + struct list_head *list2 = &tsk->robust_list2;

-#ifdef CONFIG_COMPAT - if (unlikely(tsk->compat_robust_list)) { - exit_robust_list32(tsk); - tsk->compat_robust_list = NULL; + /* + * Walk through the linked list, parsing robust lists and freeing the + * allocated lists + */ + if (unlikely(!list_empty(list2))) { + list_for_each_entry_safe(curr, n, list2, list) { + if (curr->head != NULL) { + if (curr->list_type == ROBUST_LIST_64BIT) + exit_robust_list64(tsk, curr->head); + else if (curr->list_type == ROBUST_LIST_32BIT) + exit_robust_list32(tsk, curr->head); + curr->head = NULL; + } + list_del_init(&curr->list); + kfree(curr); + } } -#endif + + tsk->robust_list_index = -1;

if (unlikely(!list_empty(&tsk->pi_state_list))) exit_pi_state_list(tsk); diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h index fcd1617212eed0e3c2367d2b463a0e019eda6d13..67201e51fa1798a21ff68f60b1e35977b9bd267b 100644 --- a/kernel/futex/futex.h +++ b/kernel/futex/futex.h @@ -467,6 +467,11 @@ extern int __futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, extern int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset);

+extern long do_set_robust_list2(struct robust_list_head __user *head, + int index, unsigned int type); + +extern struct robust_list_head __user *get_robust_list2(int index, struct task_struct *task); + /** * struct futex_vector - Auxiliary struct for futex_waitv() * @w: Userspace provided data diff --git a/kernel/futex/syscalls.c b/kernel/futex/syscalls.c index dba193dfd216cc929c8f4d979aa2bcd99237e2d8..56ee1123cbd8ea26c8d22aa74e5faed2974ec577 100644 --- a/kernel/futex/syscalls.c +++ b/kernel/futex/syscalls.c @@ -20,6 +20,18 @@ * the list. There can only be one such pending lock. */

+#ifdef CONFIG_64BIT +static inline int robust_list_native_type(void) +{ + return ROBUST_LIST_64BIT; +} +#else +static inline int robust_list_native_type(void) +{ + return ROBUST_LIST_32BIT; +} +#endif + /** * sys_set_robust_list() - Set the robust-futex list head of a task * @head: pointer to the list-head @@ -28,17 +40,63 @@ SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head, size_t, len) { + unsigned int type = robust_list_native_type(); + int ret; + /* * The kernel knows only one size for now: */ if (unlikely(len != sizeof(*head))) return -EINVAL;

- current->robust_list = head; + ret = do_set_robust_list2(head, current->robust_list_index, type); + if (ret < 0) + return ret; + + current->robust_list_index = ret;

return 0; }

+#define ROBUST_LIST_FLAGS ROBUST_LIST_TYPE_MASK + +/* + * sys_set_robust_list2() + * + * When index == -1, create a new list for user. When index >= 0, try to find + * the corresponding list and re-set the head there. + * + * Return values: + * >= 0: success, index of the robust list + * -EINVAL: invalid flags, invalid index + * -ENOENT: requested index no where to be found + * -ENOMEM: error allocating new list + * -ESRCH: too many allocated lists + */ +SYSCALL_DEFINE3(set_robust_list2, struct robust_list_head __user *, head, + int, index, unsigned int, flags) +{ + unsigned int type; + + type = flags & ROBUST_LIST_TYPE_MASK; + + if (index < -1 || index >= ROBUST_LISTS_PER_TASK) + return -EINVAL; + + if ((flags & ~ROBUST_LIST_FLAGS) != 0) + return -EINVAL; + + if (((uintptr_t) head % sizeof(u32)) != 0) + return -EINVAL; + +#ifndef CONFIG_64BIT + if (type == ROBUST_LIST_64BIT) + return -EINVAL; +#endif + + return do_set_robust_list2(head, index, type); +} + /** * sys_get_robust_list() - Get the robust-futex list head of a task * @pid: pid of the process [zero for current task] @@ -52,6 +110,7 @@ SYSCALL_DEFINE3(get_robust_list, int, pid, struct robust_list_head __user *head; unsigned long ret; struct task_struct *p; + int index;

rcu_read_lock();

@@ -68,9 +127,11 @@ SYSCALL_DEFINE3(get_robust_list, int, pid, if (!ptrace_may_access(p, PTRACE_MODE_READ_REALCREDS)) goto err_unlock;

- head = p->robust_list; + index = p->robust_list_index; rcu_read_unlock();

+ head = get_robust_list2(index, p); + if (put_user(sizeof(*head), len_ptr)) return -EFAULT; return put_user(head, head_ptr); @@ -443,10 +504,19 @@ COMPAT_SYSCALL_DEFINE2(set_robust_list, struct robust_list_head32 __user *, head, compat_size_t, len) { + unsigned int type = ROBUST_LIST_32BIT; + int ret; + if (unlikely(len != sizeof(*head))) return -EINVAL;

- current->compat_robust_list = head; + ret = do_set_robust_list2((struct robust_list_head __user *) head, + current->robust_list_index, type); + if (ret < 0) + return ret; + + current->robust_list_index = ret; +

return 0; } @@ -458,6 +528,7 @@ COMPAT_SYSCALL_DEFINE3(get_robust_list, int, pid, struct robust_list_head32 __user *head; unsigned long ret; struct task_struct *p; + int index;

rcu_read_lock();

@@ -474,9 +545,11 @@ COMPAT_SYSCALL_DEFINE3(get_robust_list, int, pid, if (!ptrace_may_access(p, PTRACE_MODE_READ_REALCREDS)) goto err_unlock;

- head = p->compat_robust_list; + index = p->compat_robust_list_index; rcu_read_unlock();

+ head = (struct robust_list_head32 __user *) get_robust_list2(index, p); + if (put_user(sizeof(*head), len_ptr)) return -EFAULT; return put_user(ptr_to_compat(head), head_ptr);

Remove the limit of ROBUST_LIST_LIMIT elements that a robust list can have, for the ones created with the new interface. This is done by overwritten the list as it's proceeded in a way that we avoid circular lists.

For the old interface, we keep the limited behavior to avoid changing the API.

Signed-off-by: André Almeida andrealmeid@igalia.com --- kernel/futex/core.c | 50 ++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 36 insertions(+), 14 deletions(-)

diff --git a/kernel/futex/core.c b/kernel/futex/core.c index 49b3bc592948a811f995017027f33ad8f285531f..61f0b48a2bcd8ab926754980ab3454b9ec13a344 100644 --- a/kernel/futex/core.c +++ b/kernel/futex/core.c @@ -1152,7 +1152,8 @@ static inline int fetch_robust_entry(struct robust_list __user **entry, * We silently return on any sign of list-walking problem. */ static void exit_robust_list64(struct task_struct *curr, - struct robust_list_head __user *head) + struct robust_list_head __user *head, + bool destroyable) { struct robust_list __user *entry, *next_entry, *pending; unsigned int limit = ROBUST_LIST_LIMIT, pi, pip; @@ -1196,13 +1197,17 @@ static void exit_robust_list64(struct task_struct *curr, } if (rc) return; - entry = next_entry; - pi = next_pi; + /* * Avoid excessively long or circular lists: */ - if (!--limit) + if (!destroyable && !--limit) break; + else + put_user(&head->list, &entry->next); + + entry = next_entry; + pi = next_pi;

cond_resched(); } @@ -1214,7 +1219,8 @@ static void exit_robust_list64(struct task_struct *curr, } #else static void exit_robust_list64(struct task_struct *curr, - struct robust_list_head __user *head) + struct robust_list_head __user *head, + bool destroyable) { pr_warn("32bit kernel should not allow ROBUST_LIST_64BIT"); } @@ -1252,7 +1258,8 @@ fetch_robust_entry32(u32 *uentry, struct robust_list __user **entry, * We silently return on any sign of list-walking problem. */ static void exit_robust_list32(struct task_struct *curr, - struct robust_list_head32 __user *head) + struct robust_list_head32 __user *head, + bool destroyable) { struct robust_list __user *entry, *next_entry, *pending; unsigned int limit = ROBUST_LIST_LIMIT, pi, pip; @@ -1301,14 +1308,17 @@ static void exit_robust_list32(struct task_struct *curr, } if (rc) return; - uentry = next_uentry; - entry = next_entry; - pi = next_pi; /* * Avoid excessively long or circular lists: */ - if (!--limit) + if (!destroyable && !--limit) break; + else + put_user((struct robust_list __user *) &head->list, &entry->next); + + uentry = next_uentry; + entry = next_entry; + pi = next_pi;

cond_resched(); } @@ -1474,26 +1484,38 @@ static void exit_pi_state_list(struct task_struct *curr) static inline void exit_pi_state_list(struct task_struct *curr) { } #endif

+/* + * futex_cleanup - After the task exists, process the robust lists + * + * Walk through the linked list, parsing robust lists and freeing the + * allocated lists. Lists created with the set_robust_list2 don't have a limit + * for sizing and can be destroyed while we walk on it to avoid circular list. + */ static void futex_cleanup(struct task_struct *tsk) { struct robust_list2_entry *curr, *n; struct list_head *list2 = &tsk->robust_list2; + bool destroyable = true; + int i = 0;

/* - * Walk through the linked list, parsing robust lists and freeing the - * allocated lists */ if (unlikely(!list_empty(list2))) { list_for_each_entry_safe(curr, n, list2, list) { + destroyable = true; + if (tsk->robust_list_index == i) + destroyable = false; + if (curr->head != NULL) { if (curr->list_type == ROBUST_LIST_64BIT) - exit_robust_list64(tsk, curr->head); + exit_robust_list64(tsk, curr->head, destroyable); else if (curr->list_type == ROBUST_LIST_32BIT) - exit_robust_list32(tsk, curr->head); + exit_robust_list32(tsk, curr->head, destroyable); curr->head = NULL; } list_del_init(&curr->list); kfree(curr); + i++; } }