From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on starla X-Spam-Level: X-Spam-Status: No, score=-0.7 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 4F0D61F461 for ; Thu, 25 Apr 2024 20:45:16 +0000 (UTC) Authentication-Results: dcvr.yhbt.net; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=igalia.com header.i=@igalia.com header.a=rsa-sha256 header.s=20170329 header.b=Lt2kjDsz; dkim-atps=neutral Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 424DB384AB56 for ; Thu, 25 Apr 2024 20:45:15 +0000 (GMT) Received: from fanzine2.igalia.com (fanzine.igalia.com [178.60.130.6]) by sourceware.org (Postfix) with ESMTPS id 91D353858C42 for ; Thu, 25 Apr 2024 20:44:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 91D353858C42 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=igalia.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=igalia.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 91D353858C42 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=178.60.130.6 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1714077887; cv=none; b=KfuGL/gC/tbNCTq8Iw/7+EJGB3Kh65yL3oKdKI/hWsPmoH70HjNEK5K6IRmRUSnOVQa7m9doeRWNX1Ov+9prEc20qPU13BsBweEAqKWm3rH3IypmLE2Z5qlpXOqp5s3V9ZiGjdv4DLrw1uMOlAJPB+ETPlSSv3Ae8iDIpdtAUtI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1714077887; c=relaxed/simple; bh=WyRKRpDdDWspxjCjUuscQqnxFO2RBD2WTOpPg6Fwpw0=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=h3CTwEfimmPWykxeZxgPVpvLRIPiO4A1/gPjB4xmHhouIydhUhLMgkrqWsBT4LnOcyNSrlsWWVlhvBhd2Om/VyTR1Y5xE5V5hAt+LOaTd7fVOxI+Gd+lsc2VyYxGVP2Sf55AdcazsIY28f8QXf0sc7ZZJcTe/p0tb0YgfOqGU0E= ARC-Authentication-Results: i=1; server2.sourceware.org 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: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: In-Reply-To:References:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=tq5X8zmN+3k5A79fjsOahtoee5I5v66qJtvAbIOuA/0=; b=Lt2kjDszrhUtpDwANofp1SHp1c Tdsdb8Mbw2ACXHtyZvmIRF2ickkBKO0xNEKrwZiflhZQNJS4JkvSEvt+GRGkh+jfzdN6G22QEyX2T 1YfaIyTpjgZ+nh7tkY8ZpI+jOXcO8OvLb53EpbaiDrkbp1nix/fMCmmBisSQ9S1LuCo5EXvRv3iJ0 XfxyUt6lRoVwRlTa0gqDxKUlW97ExfduqAePjzuVTvYOk4iTOaiqXYlniMQZvXXJ7GFOhP4Pa0xcL eQzSdrcgb+TlND+gC3Qz9tF5iMwZqZE8qIAT2QX2pCKweoCimN1CrgsK5ydJq1qvbSFgvwaskPJSQ uFjrzW7Q==; Received: from 201-42-129-95.dsl.telesp.net.br ([201.42.129.95] helo=steammachine.lan) by fanzine2.igalia.com with esmtpsa (Cipher TLS1.3:ECDHE_X25519__RSA_PSS_RSAE_SHA256__AES_256_GCM:256) (Exim) id 1s05wW-008iV5-LF; Thu, 25 Apr 2024 22:43:45 +0200 From: =?UTF-8?q?Andr=C3=A9=20Almeida?= To: Mathieu Desnoyers , Peter Zijlstra , Thomas Gleixner Cc: linux-kernel@vger.kernel.org, "Paul E . McKenney" , "Boqun Feng" , "H . Peter Anvin" , "Paul Turner" , linux-api@vger.kernel.org, "Christian Brauner" , "Florian Weimer" , David.Laight@ACULAB.COM, carlos@redhat.com, "Peter Oskolkov" , "Alexander Mikhalitsyn" , "Chris Kennelly" , "Ingo Molnar" , "Darren Hart" , "Davidlohr Bueso" , =?UTF-8?q?Andr=C3=A9=20Almeida?= , libc-alpha@sourceware.org, "Steven Rostedt" , "Jonathan Corbet" , "Noah Goldstein" , "Daniel Colascione" , longman@redhat.com, kernel-dev@igalia.com Subject: [RFC PATCH 0/1] Add FUTEX_SPIN operation Date: Thu, 25 Apr 2024 17:43:31 -0300 Message-ID: <20240425204332.221162-1-andrealmeid@igalia.com> X-Mailer: git-send-email 2.44.0 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Hi, In the last LPC, Mathieu Desnoyers and I presented[0] a proposal to extend the rseq interface to be able to implement spin locks in userspace correctly. Thomas Gleixner agreed that this is something that Linux could improve, but asked for an alternative proposal first: a futex operation that allows to spin a user lock inside the kernel. This patchset implements a prototype of this idea for further discussion. With FUTEX2_SPIN flag set during a futex_wait(), the futex value is expected to be the PID of the lock owner. Then, the kernel gets the task_struct of the corresponding PID, and checks if it's running. It spins until the futex is awaken, the task is scheduled out or if a timeout happens. If the lock owner is scheduled out at any time, then the syscall follows the normal path of sleeping as usual. If the futex is awaken and we are spinning, we can return to userspace quickly, avoid the scheduling out and in again to wake from a futex_wait(), thus speeding up the wait operation. I didn't manage to find a good mechanism to prevent race conditions between setting *futex = PID in userspace and doing find_get_task_by_vpid(PID) in kernel space, giving that there's enough room for the original PID owner exit and such PID to be relocated to another unrelated task in the system. I didn't performed benchmarks so far, as I hope to clarify if this interface makes sense prior to doing measurements on it. This implementation has some debug prints to make it easy to inspect what the kernel is doing, so you can check if the futex woke during spinning or if just slept as the normal path: [ 6331] futex_spin: spinned 64738 times, sleeping [ 6331] futex_spin: woke after 1864606 spins [ 6332] futex_spin: woke after 1820906 spins [ 6351] futex_spin: spinned 1603293 times, sleeping [ 6352] futex_spin: woke after 1848199 spins [0] https://lpc.events/event/17/contributions/1481/ You can find a small snippet to play with this interface here: --- /* * futex2_spin example, by André Almeida * * gcc spin.c -o spin */ #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include #define __NR_futex_wake 454 #define __NR_futex_wait 455 #define WAKE_WAIT_US 10000 #define FUTEX2_SPIN 0x08 #define STACK_SIZE (1024 * 1024) #define FUTEX2_SIZE_U32 0x02 #define FUTEX2_PRIVATE FUTEX_PRIVATE_FLAG #define timeout_ns 30000000 void *futex; static inline int futex2_wake(volatile void *uaddr, unsigned long mask, int nr, unsigned int flags) { return syscall(__NR_futex_wake, uaddr, mask, nr, flags); } static inline int futex2_wait(volatile void *uaddr, unsigned long val, unsigned long mask, unsigned int flags, struct timespec *timo, clockid_t clockid) { return syscall(__NR_futex_wait, uaddr, val, mask, flags, timo, clockid); } void waiter_fn() { struct timespec to; unsigned int flags = FUTEX2_PRIVATE | FUTEX2_SIZE_U32 | FUTEX2_SPIN; uint32_t child_pid = *(uint32_t *) futex; clock_gettime(CLOCK_MONOTONIC, &to); to.tv_nsec += timeout_ns; if (to.tv_nsec >= 1000000000) { to.tv_sec++; to.tv_nsec -= 1000000000; } printf("waiting on PID %d...\n", child_pid); if (futex2_wait(futex, child_pid, ~0U, flags, &to, CLOCK_MONOTONIC)) printf("waiter failed errno %d\n", errno); puts("waiting done"); } int function(int n) { return n + n; } #define CHILD_LOOPS 500000 static int child_fn(void *arg) { int i, n = 2; for (i = 0; i < CHILD_LOOPS; i++) n = function(n); futex2_wake(futex, ~0U, 1, FUTEX2_SIZE_U32 | FUTEX_PRIVATE_FLAG); puts("child thread is done"); return 0; } int main() { uint32_t child_pid = 0; char *stack; futex = &child_pid; stack = mmap(NULL, STACK_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK, -1, 0); if (stack == MAP_FAILED) err(EXIT_FAILURE, "mmap"); child_pid = clone(child_fn, stack + STACK_SIZE, CLONE_VM, NULL); waiter_fn(); usleep(WAKE_WAIT_US * 10); return 0; } --- André Almeida (1): futex: Add FUTEX_SPIN operation include/uapi/linux/futex.h | 2 +- kernel/futex/futex.h | 6 ++- kernel/futex/waitwake.c | 79 +++++++++++++++++++++++++++++++++++++- 3 files changed, 83 insertions(+), 4 deletions(-) -- 2.44.0