From nobody Sun Feb 8 17:04:09 2026 Received: from fanzine2.igalia.com (fanzine.igalia.com [178.60.130.6]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 985B8BA50 for ; Fri, 10 Jan 2025 20:05:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=178.60.130.6 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539539; cv=none; b=VEfIfA1a/7KVzgckWDB9s7y6m5/C1+S6wFt57jDb9BKaXIU8qxGpA0ENMxP+ePJepg0UwbB/goQng7CJfx6XN5OYrC+wii5c8qJtxyhswjYjeA9q/pTwL8CBCjkb6I2EIPgqncbjUaoA/eL6ff8mLfeyYOmk/5h1EByCdRPfZ7A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539539; c=relaxed/simple; bh=zWHeteOv9ViJxKSjsnihyr65MydGr4v/vyFDhahDO/Q=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=Af02PmuyNxngxVtiqwFYqiqvZaHB1igZSwdahghEpwcl/aQ4As3DspQ5PszcuLB/T5UUV0aOZpkqaXG9/bxNzDczirizGAKH2N/aYdxV6ycfQMTugcCE0p5hMoOl9NR6c8Cbl9hE+Z8c38nt3Snf4U7EMQtBsQ4B4NVw9RaI9VY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com; spf=pass smtp.mailfrom=igalia.com; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b=Xm3AqaAH; arc=none smtp.client-ip=178.60.130.6 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=igalia.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b="Xm3AqaAH" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=igalia.com; s=20170329; h=Content-Transfer-Encoding:Content-Type:MIME-Version:References: In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=+WT1EI/mf4t3im9EMJx2EAn582dhEPR0PPEK1dMiVOs=; b=Xm3AqaAHp1fEAc4VinOowhuTM6 8QHdmH1S406BFn7+2zZ1u985NpnDLhxSOXXsCtFI+A8lanvchaNvjhCD54DRIxsiwRDb0gx+1gjJ3 bM/4jIVZN6JToSYxsjQQefSnKNcBGKYRc0s4spwXwc7/nPW9SkCxSDUx5VGmzSTgP3hWQKGONqLms rP8RbQaURF9wpmQzFmAVYqa5HPE32QCsqER4K+pq/JCvTrwfs9ZbSzKgqQX6xA4jCPWjsXEjF6WN6 dnXitCTg0e2kQuONG1fmxSwE2aYRnb06zFEBZ/WlRg5To5xEMX0ByIVIrpAWl8XN8QaEIA5+BD5v9 3hZe7Y5Q==; Received: from [177.139.21.57] (helo=localhost.localdomain) by fanzine2.igalia.com with esmtpsa (Cipher TLS1.3:ECDHE_X25519__RSA_PSS_RSAE_SHA256__AES_256_GCM:256) (Exim) id 1tWLFt-00E827-Iz; Fri, 10 Jan 2025 21:05:18 +0100 From: =?UTF-8?q?Andr=C3=A9=20Almeida?= To: Thomas Gleixner , Ingo Molnar , Peter Zijlstra , Darren Hart , Davidlohr Bueso , Arnd Bergmann , Florian Weimer Cc: linux-kernel@vger.kernel.org, kernel-dev@igalia.com, Vinicius Peixoto , =?UTF-8?q?Andr=C3=A9=20Almeida?= Subject: [PATCH 1/4] futex: Drop ROBUST_LIST_LIMIT Date: Fri, 10 Jan 2025 17:05:05 -0300 Message-ID: <20250110200508.353290-2-andrealmeid@igalia.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250110200508.353290-1-andrealmeid@igalia.com> References: <20250110200508.353290-1-andrealmeid@igalia.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable ROBUST_LIST_LIMIT was introduced to avoid the kernel get stuck in circular lists, stopping to handle locks after the limit. This could cause starvation in applications that have very long lists with valid and non repetitive elements. Instead of having a hard limit, rewrite the next pointer list while walking on it. In this way, if the kernel ever revisits a repetitive element (characterizing a circular list) the loop will stop. Signed-off-by: Andr=C3=A9 Almeida --- include/uapi/linux/futex.h | 3 +-- kernel/futex/core.c | 13 +++++++------ 2 files changed, 8 insertions(+), 8 deletions(-) diff --git a/include/uapi/linux/futex.h b/include/uapi/linux/futex.h index 13903a278b71..4d2cd97a6ce5 100644 --- a/include/uapi/linux/futex.h +++ b/include/uapi/linux/futex.h @@ -189,8 +189,7 @@ struct robust_list2_entry { #define FUTEX_TID_MASK 0x3fffffff =20 /* - * This limit protects against a deliberately circular list. - * (Not worth introducing an rlimit for it) + * Deprecated, do not use. There is no limit of items in a list. */ #define ROBUST_LIST_LIMIT 2048 =20 diff --git a/kernel/futex/core.c b/kernel/futex/core.c index f8962bc27c90..772c26901ec6 100644 --- a/kernel/futex/core.c +++ b/kernel/futex/core.c @@ -779,7 +779,7 @@ static void exit_robust_list64(struct task_struct *curr, struct robust_list_head __user *head) { struct robust_list __user *entry, *next_entry, *pending; - unsigned int limit =3D ROBUST_LIST_LIMIT, pi, pip; + unsigned int pi, pip; unsigned int next_pi; unsigned long futex_offset; int rc; @@ -820,13 +820,14 @@ static void exit_robust_list64(struct task_struct *cu= rr, } if (rc) return; - entry =3D next_entry; - pi =3D next_pi; + /* - * Avoid excessively long or circular lists: + * Avoid circular lists: */ - if (!--limit) - break; + put_user(&head->list, &entry->next); + + entry =3D next_entry; + pi =3D next_pi; =20 cond_resched(); } --=20 2.47.1 From nobody Sun Feb 8 17:04:09 2026 Received: from fanzine2.igalia.com (fanzine.igalia.com [178.60.130.6]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9AC50158DC4 for ; Fri, 10 Jan 2025 20:05:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=178.60.130.6 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539539; cv=none; b=LdfJJMtC/HOMwGtODKCGIIFNouMQ60jCXiccTMRkLnM5T7MHH4aSKiOc+kzYzN0ldut9NSymwvJ+i3yjXjtUIvc7GcO9SsQYZuusexDAShV+oCPL/eqHesWwaCcKU3TlRV5qxtXIX+xsg/NzPCZSZ14HEzWW3VDB+kXE2tja/PQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539539; c=relaxed/simple; bh=Bkf1kQ5N13iXuGGknQQh06++n04kjlps5mSLYTQleoM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=kEbadlpGev3/MepxZx63QHj0c7q+jsGy4R/EY8MI/NGQx8dleyIVGbZYPzcAUj/bHVfmD6STZnHsrBqcg6bLS/8Zm+C18wBx3mV7XDD5yhsGjWfFYrPX1xInX9bySavlLNAwCFfRx3rVfKQDRl9IMckfaqgdntwxuoyHZIwY2V0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com; spf=pass smtp.mailfrom=igalia.com; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b=QKbiOqIw; arc=none smtp.client-ip=178.60.130.6 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=igalia.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b="QKbiOqIw" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=igalia.com; s=20170329; h=Content-Transfer-Encoding:Content-Type:MIME-Version:References: In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=j8PCbgWbhVazCv/Tivq4sfQeyqPfFSWqIk1/pr7ejjA=; b=QKbiOqIwUhEEUH2Lh9K0MlNXz8 eWNAlZcoJO5+8ejycgPU5GjQCHH1IgSyjV+9NW8NOA/ZqsIk28J8qWrkhDxUwqkC1DeurI1yWgRbC Y+FBjWiRc5ZWrooeHeg2QgGfeia3CuFLmQC7dxsIJuKcvIkj6hb9W3M+pysjen1YyeC/YTHvn04n9 VSgAJT0p2kxYW3p+t8WP3/CvmLKh9MwEtQNw4nw7IcPbf4YG9fl9uWPAUFSC98f6Y9jX5UlczysFe dPFM+WlwqkIOyRfIp8JLxn8cSiKGMTSrRx6Es2lIfrAygnN3AICNae+TORYrghCM7voIg9yuhhCiN H80/OGtw==; Received: from [177.139.21.57] (helo=localhost.localdomain) by fanzine2.igalia.com with esmtpsa (Cipher TLS1.3:ECDHE_X25519__RSA_PSS_RSAE_SHA256__AES_256_GCM:256) (Exim) id 1tWLFw-00E827-Re; Fri, 10 Jan 2025 21:05:21 +0100 From: =?UTF-8?q?Andr=C3=A9=20Almeida?= To: Thomas Gleixner , Ingo Molnar , Peter Zijlstra , Darren Hart , Davidlohr Bueso , Arnd Bergmann , Florian Weimer Cc: linux-kernel@vger.kernel.org, kernel-dev@igalia.com, Vinicius Peixoto , =?UTF-8?q?Andr=C3=A9=20Almeida?= Subject: [PATCH 2/4] selftests/futex: Add ASSERT_ macros Date: Fri, 10 Jan 2025 17:05:06 -0300 Message-ID: <20250110200508.353290-3-andrealmeid@igalia.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250110200508.353290-1-andrealmeid@igalia.com> References: <20250110200508.353290-1-andrealmeid@igalia.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Create ASSERT_{EQ, NE, TRUE, FALSE} macros to make test creation easier. Signed-off-by: Andr=C3=A9 Almeida --- .../testing/selftests/futex/include/logging.h | 38 +++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/tools/testing/selftests/futex/include/logging.h b/tools/testin= g/selftests/futex/include/logging.h index 874c69ce5cce..a19755622a87 100644 --- a/tools/testing/selftests/futex/include/logging.h +++ b/tools/testing/selftests/futex/include/logging.h @@ -23,6 +23,44 @@ #include #include "kselftest.h" =20 +#define ASSERT_EQ(var, value) \ +do { \ + if (var !=3D value) { \ + ksft_test_result_fail("%s: expected %ld, but %s has %ld\n", \ + __func__, (long) value, #var, \ + (long) var); \ + return; \ + } \ +} while (0) + +#define ASSERT_NE(var, value) \ +do { \ + if (var =3D=3D value) { \ + ksft_test_result_fail("%s: expected not %ld, but %s has %ld\n", \ + __func__, (long) value, #var, \ + (long) var); \ + return; \ + } \ +} while (0) + +#define ASSERT_TRUE(var) \ +do { \ + if ((var) =3D=3D 0) { \ + ksft_test_result_fail("%s: expected %s to be true\n", \ + __func__, #var); \ + return; \ + } \ +} while (0) + +#define ASSERT_FALSE(var) \ +do { \ + if (var) { \ + ksft_test_result_fail("%s: expected %s to be false\n", \ + __func__, #var); \ + return; \ + } \ +} while (0) + /* * Define PASS, ERROR, and FAIL strings with and without color escape * sequences, default to no color. --=20 2.47.1 From nobody Sun Feb 8 17:04:09 2026 Received: from fanzine2.igalia.com (fanzine.igalia.com [178.60.130.6]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 15BA72066CB for ; Fri, 10 Jan 2025 20:05:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=178.60.130.6 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539542; cv=none; b=txpFNHkSFz9giOW0iA2TUgymQ5Lvw2oxeJEWfL/VFJ1Y5xKQ35YkvSlElxrbNvby9kXuGE3XYWz0pgx7UcjLcR9d3S07LCEJzXHqoh61/JiLqsDawHM1SYOjtFAG7jqvYk1vh94uEV0wLDWg9oA40+h6+e4Ti5q9YJ066VoBNAo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539542; c=relaxed/simple; bh=iRNQK8SxBiu7XfzuyvIkRB/hqeVVYN6otr9/nLbpIEg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=AfpnyIPHqvxOhjh2dmGE7DmatNvlnKuYSJNi3GkIb+hq1BSPZ/cOJovmzev5v1qQkn0DClhgCm74WuQccWBzEnLH4q1N+lo2rjcFBjce9ym92/u3t2DDuNgbBSi597ceZUOsDr4+FHlAEGkKcL8OjcE5NsemukqoEd+iYOrKHxE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com; spf=pass smtp.mailfrom=igalia.com; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b=LW4ctyF0; arc=none smtp.client-ip=178.60.130.6 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=igalia.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b="LW4ctyF0" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=igalia.com; s=20170329; h=Content-Transfer-Encoding:Content-Type:MIME-Version:References: In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=YrE9f/j0DOzK8DarzgzPoRs3YBlx3WnyfwH7KOsDuwU=; b=LW4ctyF0eaF9wa2+hF8zkaVbPV 0IygGV0MT/3KpOJSQ8i3+QzzuWz/IrsKjkwzyZAJBd4jkbDA3iF4IxDGXzPc8jhyOPltFwxP6SX+V wuHEn9dS71kKuF/L6ER0jGGkcg71g+2nTOBVK0lF55zaEJtZAURAWRBk9z1oSYtWhpOFj07F1NeTX nZ2yrdFK//w14vfoTwZ7mZUiaWncRl/utxJimi9FPjI+EeFIT0ShrCcEcBa62SJMeQTqjO68uTvBu d3zLkQkMHRN0uAu05O3R0zgl8Gn/aMQ3t/+G11c8Aps3v2UH3CYcjH0HQEXHILLR6ed0NhOCBVx9t ROhohE+Q==; Received: from [177.139.21.57] (helo=localhost.localdomain) by fanzine2.igalia.com with esmtpsa (Cipher TLS1.3:ECDHE_X25519__RSA_PSS_RSAE_SHA256__AES_256_GCM:256) (Exim) id 1tWLG0-00E827-43; Fri, 10 Jan 2025 21:05:24 +0100 From: =?UTF-8?q?Andr=C3=A9=20Almeida?= To: Thomas Gleixner , Ingo Molnar , Peter Zijlstra , Darren Hart , Davidlohr Bueso , Arnd Bergmann , Florian Weimer Cc: linux-kernel@vger.kernel.org, kernel-dev@igalia.com, Vinicius Peixoto , =?UTF-8?q?Andr=C3=A9=20Almeida?= Subject: [PATCH 3/4] selftests/futex: Create test for robust list Date: Fri, 10 Jan 2025 17:05:07 -0300 Message-ID: <20250110200508.353290-4-andrealmeid@igalia.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250110200508.353290-1-andrealmeid@igalia.com> References: <20250110200508.353290-1-andrealmeid@igalia.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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` Signed-off-by: Andr=C3=A9 Almeida --- Changes from v2: - Dropped kselftest_harness include, using just futex test API - This is the expected output: TAP version 13 1..6 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 # Totals: pass:6 fail:0 xfail:0 xpass:0 skip:0 error:0 Changes from v1: - Change futex type from int to _Atomic(unsigned int) - Use old futex(FUTEX_WAIT) instead of the new sys_futex_wait() --- .../selftests/futex/functional/.gitignore | 1 + .../selftests/futex/functional/Makefile | 3 +- .../selftests/futex/functional/robust_list.c | 516 ++++++++++++++++++ 3 files changed, 519 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/futex/functional/robust_list.c diff --git a/tools/testing/selftests/futex/functional/.gitignore b/tools/te= sting/selftests/futex/functional/.gitignore index fbcbdb6963b3..4726e1be7497 100644 --- a/tools/testing/selftests/futex/functional/.gitignore +++ b/tools/testing/selftests/futex/functional/.gitignore @@ -9,3 +9,4 @@ futex_wait_wouldblock futex_wait futex_requeue futex_waitv +robust_list diff --git a/tools/testing/selftests/futex/functional/Makefile b/tools/test= ing/selftests/futex/functional/Makefile index f79f9bac7918..b8635a1ac7f6 100644 --- a/tools/testing/selftests/futex/functional/Makefile +++ b/tools/testing/selftests/futex/functional/Makefile @@ -17,7 +17,8 @@ TEST_GEN_PROGS :=3D \ futex_wait_private_mapped_file \ futex_wait \ futex_requeue \ - futex_waitv + futex_waitv \ + robust_list =20 TEST_PROGS :=3D run.sh =20 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 000000000000..bd4437c6aebb --- /dev/null +++ b/tools/testing/selftests/futex/functional/robust_list.c @@ -0,0 +1,516 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Copyright (C) 2024 Igalia S.L. + * + * Robust list test by Andr=C3=A9 Almeida + * + * 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 wai= ting + * 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 al= l the + * locks (futexes) that it is holding. The robust list is a linked list, a= nd + * userspace register the start of the list with the syscall set_robust_li= st(). + * 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 +#include +#include +#include +#include +#include +#include +#include + +#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_p= tr) +{ + return syscall(SYS_get_robust_list, pid, head, len_ptr); +} + +/* + * Basic lock struct, contains just the futex word and the robust list ele= ment + * 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 su= ccess + */ +static int create_child(int (*fn)(void *arg), void *arg) +{ + char *stack; + pid_t pid; + + stack =3D mmap(NULL, STACK_SIZE, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK, -1, 0); + if (stack =3D=3D MAP_FAILED) + return -1; + + stack +=3D STACK_SIZE; + + pid =3D clone(fn, stack, CLONE_VM | SIGCHLD, arg); + + if (pid =3D=3D -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 =3D set_robust_list(head, sizeof(struct robust_list_head)); + if (ret) + return ret; + + head->futex_offset =3D (size_t) offsetof(struct lock_struct, futex) - + (size_t) offsetof(struct lock_struct, list); + head->list.next =3D &head->list; + head->list_op_pending =3D NULL; + + return 0; +} + +/* + * A basic (and incomplete) mutex lock function with robustness + */ +static int mutex_lock(struct lock_struct *lock, struct robust_list_head *h= ead, bool error_inject) +{ + _Atomic(unsigned int) *futex =3D &lock->futex; + unsigned int zero =3D 0; + int ret =3D -1; + pid_t tid =3D 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 =3D &lock->list; + + if (atomic_compare_exchange_strong(futex, &zero, tid)) { + /* + * We took the lock, insert it in the robust list + */ + struct robust_list *list =3D &head->list; + + /* Error injection to test list_op_pending */ + if (error_inject) + return 0; + + while (list->next !=3D &head->list) + list =3D list->next; + + list->next =3D &lock->list; + lock->list.next =3D &head->list; + + ret =3D 0; + } else { + /* + * We didn't take the lock, wait until the owner wakes (or dies) + */ + struct timespec to; + + to.tv_sec =3D FUTEX_TIMEOUT; + to.tv_nsec =3D 0; + + tid =3D atomic_load(futex); + /* Kernel ignores futexes without the waiters flag */ + tid |=3D FUTEX_WAITERS; + atomic_store(futex, tid); + + ret =3D 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 =3D NULL; + + return ret; +} + +/* + * This child thread will succeed taking the lock, and then will exit hold= ing it + */ +static int child_fn_lock(void *arg) +{ + struct lock_struct *lock =3D (struct lock_struct *) arg; + struct robust_list_head head; + int ret; + + ret =3D set_list(&head); + if (ret) + ksft_test_result_fail("set_robust_list error\n"); + + ret =3D 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, regis= ter 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 =3D { .futex =3D 0 }; + struct robust_list_head head; + _Atomic(unsigned int) *futex =3D &lock.futex; + int ret; + + ret =3D set_list(&head); + ASSERT_EQ(ret, 0); + + /* + * Lets use a barrier to ensure that the child thread takes the lock + * before the parent + */ + ret =3D pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + + ret =3D create_child(&child_fn_lock, &lock); + ASSERT_NE(ret, -1); + + pthread_barrier_wait(&barrier); + ret =3D 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 !=3D 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 =3D sizeof(struct robust_list_head); + int ret; + + ret =3D set_robust_list(&head, head_size); + ASSERT_EQ(ret, 0); + + ret =3D set_robust_list(&head, head_size * 2); + ASSERT_EQ(ret, -1); + ASSERT_EQ(errno, EINVAL); + + ret =3D set_robust_list(&head, head_size - 1); + ASSERT_EQ(ret, -1); + ASSERT_EQ(errno, EINVAL); + + ret =3D 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 =3D 0, getting the list of the running th= read + */ +static void test_get_robust_list_self(void) +{ + struct robust_list_head head, head2, *get_head; + size_t head_size =3D sizeof(struct robust_list_head), len_ptr; + int ret; + + ret =3D set_robust_list(&head, head_size); + ASSERT_EQ(ret, 0); + + ret =3D get_robust_list(0, &get_head, &len_ptr); + ASSERT_EQ(ret, 0); + ASSERT_EQ(get_head, &head); + ASSERT_EQ(head_size, len_ptr); + + ret =3D set_robust_list(&head2, head_size); + ASSERT_EQ(ret, 0); + + ret =3D 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 =3D (struct robust_list_head *) arg; + int ret; + + ret =3D 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 e= nsure + * 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 =3D pthread_barrier_init(&barrier, NULL, 2); + ret =3D pthread_barrier_init(&barrier2, NULL, 2); + ASSERT_EQ(ret, 0); + + tid =3D create_child(&child_list, &head); + ASSERT_NE(tid, -1); + + pthread_barrier_wait(&barrier); + + ret =3D 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 =3D (struct lock_struct *) arg; + struct robust_list_head head; + int ret; + + ret =3D set_list(&head); + if (ret) + ksft_test_result_fail("set_robust_list error\n"); + + ret =3D 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() exi= ts + * earlier, just after setting list_op_pending and taking the lock, to tes= t the + * list_op_pending mechanism + */ +static void test_set_list_op_pending(void) +{ + struct lock_struct lock =3D { .futex =3D 0 }; + struct robust_list_head head; + _Atomic(unsigned int) *futex =3D &lock.futex; + int ret; + + ret =3D set_list(&head); + ASSERT_EQ(ret, 0); + + ret =3D pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + + ret =3D create_child(&child_fn_lock_with_error, &lock); + ASSERT_NE(ret, -1); + + pthread_barrier_wait(&barrier); + ret =3D mutex_lock(&lock, &head, false); + + ASSERT_EQ(ret, 0); + if (ret !=3D 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 =3D (struct lock_struct *) arg; + struct robust_list_head head; + int i; + + set_list(&head); + + for (i =3D 0; i < CHILD_NR; i++) { + locks[i].futex =3D 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 =3D (struct lock_struct *) arg; + struct robust_list_head head; + int ret; + + pthread_barrier_wait(&barrier2); + ret =3D 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 wak= e when + * the holder dies + */ +static void test_robust_list_multiple_elements(void) +{ + struct lock_struct locks[CHILD_NR]; + int i, ret; + + ret =3D pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + ret =3D 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 =3D 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__); +} + +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=3DQUIET %d=3DCRITICAL %d=3DINFO\n", + VQUIET, VCRITICAL, VINFO); +} + +int main(int argc, char *argv[]) +{ + int c; + + while ((c =3D getopt(argc, argv, "cht:v:")) !=3D -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(6); + + 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(); + + ksft_print_cnts(); + return 0; +} --=20 2.47.1 From nobody Sun Feb 8 17:04:09 2026 Received: from fanzine2.igalia.com (fanzine.igalia.com [178.60.130.6]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DCBDD206F33 for ; Fri, 10 Jan 2025 20:05:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=178.60.130.6 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539542; cv=none; b=ARfe7GpEZZjK/vFkpj/kr1pgjQsIrLtBlcnJpx9JRkx7RB+CDTT2S97rgWF7LZlWIGw/xQXfc2arDyGMpzP+dMeJr/sq2ViKfZ0xnCQbkdNdLFojkZOcEIZu/xrM3HXiL1x/KYmJ9lffIbp1ChzgADW3Q0PXcoXwkqlICvosano= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736539542; c=relaxed/simple; bh=1qbjR4kdVrrJatQtFDCKBymH1HH3oJb9mtdKzkty5N8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=IAf7djCeWFEVINnJOOXq5RXxxdqNT0/OCWwCoqb4JDmbvixozNoFXGkcXJAYmHWRLanxtBVOY4ojc3fczYnBLc1EohgX177AU33oQb4TCarG+w5rPlo1MbVu5vrtvSW12I10UXGRBrdEGa12M5pJmMHYEehzmkkwfNOGkAAD5SA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com; spf=pass smtp.mailfrom=igalia.com; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b=By1I9Cth; arc=none smtp.client-ip=178.60.130.6 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=igalia.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=igalia.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=igalia.com header.i=@igalia.com header.b="By1I9Cth" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=igalia.com; s=20170329; h=Content-Transfer-Encoding:Content-Type:MIME-Version:References: In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=L+0iS5a0BprAcQ6v1oPjoTH9/EHxYzQhmOjHvOZc9CQ=; b=By1I9Cth45DEdw5F8KkLR6d+xi +hAYjQ+WbW8TKK5bWRU17rEnCD5xOr6dm77XbGwVUiHXjb4mL++/2JuE5dTnqlFEmp6LGqcqPJ3Cv LFVNOXCPMEyUdUrxvcrjmU8L3VAXzSreS2zarKQ07mUPp8TgRrgClxXOjMHCaJGa7pfZvQ41zAW6v 4Py8h2C6tMvC//VQXwUiiihxRtCDU19BITnzE/PKWLU5B8yqsVlbcK2XAw5aubTATHhpLgGxNXTnV mo8TCSsuPa9CzIQAzTfqkC8hdBoP/q2vUp41Reipo28gg48+iCFk2Qfa2Q7VsQRHkBdmxPFPT3ZTr r4UgyCWA==; Received: from [177.139.21.57] (helo=localhost.localdomain) by fanzine2.igalia.com with esmtpsa (Cipher TLS1.3:ECDHE_X25519__RSA_PSS_RSAE_SHA256__AES_256_GCM:256) (Exim) id 1tWLG3-00E827-Jj; Fri, 10 Jan 2025 21:05:28 +0100 From: =?UTF-8?q?Andr=C3=A9=20Almeida?= To: Thomas Gleixner , Ingo Molnar , Peter Zijlstra , Darren Hart , Davidlohr Bueso , Arnd Bergmann , Florian Weimer Cc: linux-kernel@vger.kernel.org, kernel-dev@igalia.com, Vinicius Peixoto , =?UTF-8?q?Andr=C3=A9=20Almeida?= Subject: [PATCH 4/4] selftests/futex: Create tests for long and circular robust lists Date: Fri, 10 Jan 2025 17:05:08 -0300 Message-ID: <20250110200508.353290-5-andrealmeid@igalia.com> X-Mailer: git-send-email 2.47.1 In-Reply-To: <20250110200508.353290-1-andrealmeid@igalia.com> References: <20250110200508.353290-1-andrealmeid@igalia.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable After dropping ROBUST_LIST_LIMIT, create new robust list tests to ensure two conditions: - That the kernel can correctly handle circular lists - That the kernel can correctly wake up elements in very long lists, larger that the old ROBUST_LIST_LIMIT. Signed-off-by: Andr=C3=A9 Almeida --- .../selftests/futex/functional/robust_list.c | 127 +++++++++++++++++- 1 file changed, 126 insertions(+), 1 deletion(-) diff --git a/tools/testing/selftests/futex/functional/robust_list.c b/tools= /testing/selftests/futex/functional/robust_list.c index bd4437c6aebb..4bd6795b3ac5 100644 --- a/tools/testing/selftests/futex/functional/robust_list.c +++ b/tools/testing/selftests/futex/functional/robust_list.c @@ -471,6 +471,128 @@ static void test_robust_list_multiple_elements(void) ksft_test_result_pass("%s\n", __func__); } =20 +/* + * This is the old limit defined by the kernel + */ +#define ROBUST_LIST_LIMIT 2048 +#define CHILD_LIST_LIMIT (ROBUST_LIST_LIMIT + 10) + +static int child_robust_list_limit(void *arg) +{ + struct lock_struct *locks; + struct robust_list *list; + struct robust_list_head head; + int ret, i; + + locks =3D (struct lock_struct *) arg; + + ret =3D set_list(&head); + if (ret) + ksft_test_result_fail("set_list error\n"); + + /* + * Create a very long list of locks + */ + head.list.next =3D &locks[0].list; + + list =3D head.list.next; + for (i =3D 0; i < CHILD_LIST_LIMIT - 1; i++) { + list->next =3D &locks[i+1].list; + list =3D list->next; + } + list->next =3D &head.list; + + /* + * Grab the lock in the last one, and die without releasing it + */ + mutex_lock(&locks[CHILD_LIST_LIMIT], &head, false); + pthread_barrier_wait(&barrier); + + sleep(1); + + return 0; +} + +/* + * Robust list used to have a limit of 2048 items from the kernel side. Af= ter + * this limit the kernel would stop walking the list and ignore the other + * futexes, causing deadlocks. + * + * After this limit has been dropped, test if we can wait for a list of mo= re + * than 2048 elements. + */ +static void test_robust_list_limit(void) +{ + struct lock_struct locks[CHILD_LIST_LIMIT + 1]; + _Atomic(unsigned int) *futex =3D &locks[CHILD_LIST_LIMIT].futex; + struct robust_list_head head; + int ret; + + *futex =3D 0; + + ret =3D set_list(&head); + ASSERT_EQ(ret, 0); + + ret =3D pthread_barrier_init(&barrier, NULL, 2); + ASSERT_EQ(ret, 0); + + create_child(child_robust_list_limit, locks); + + /* + * After the child thread creates the very long list of locks, wait on + * the last one. + */ + pthread_barrier_wait(&barrier); + ret =3D mutex_lock(&locks[CHILD_LIST_LIMIT], &head, false); + + if (ret !=3D 0) + printf("futex wait returned %d\n", errno); + ASSERT_EQ(ret, 0); + + ASSERT_TRUE(*futex | FUTEX_OWNER_DIED); + + wait(NULL); + pthread_barrier_destroy(&barrier); + + 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 =3D set_list(&head); + if (ret) + ksft_test_result_fail("set_list error\n"); + + head.list.next =3D &a.list; + + /* + * The last element should point to head list, but we short circuit it + */ + a.list.next =3D &b.list; + b.list.next =3D &c.list; + c.list.next =3D &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 ha= ndling + * 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); @@ -502,14 +624,17 @@ int main(int argc, char *argv[]) } =20 ksft_print_header(); - ksft_set_plan(6); + ksft_set_plan(8); =20 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_robust_list_limit(); + test_circular_list(); =20 ksft_print_cnts(); return 0; --=20 2.47.1