From patchwork Sun Nov 21 21:20:35 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 12631061 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 98F68C433F5 for ; Sun, 21 Nov 2021 21:21:28 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 41CF16B0072; Sun, 21 Nov 2021 16:20:57 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 3A4016B0073; Sun, 21 Nov 2021 16:20:57 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 21E626B0074; Sun, 21 Nov 2021 16:20:57 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0210.hostedemail.com [216.40.44.210]) by kanga.kvack.org (Postfix) with ESMTP id 100096B0072 for ; Sun, 21 Nov 2021 16:20:57 -0500 (EST) Received: from smtpin16.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id CAE54824C449 for ; Sun, 21 Nov 2021 21:20:46 +0000 (UTC) X-FDA: 78834206892.16.BD1C13A Received: from mail-pj1-f53.google.com (mail-pj1-f53.google.com [209.85.216.53]) by imf29.hostedemail.com (Postfix) with ESMTP id 3CFE49001A92 for ; Sun, 21 Nov 2021 21:20:44 +0000 (UTC) Received: by mail-pj1-f53.google.com with SMTP id gb13-20020a17090b060d00b001a674e2c4a8so13508417pjb.4 for ; Sun, 21 Nov 2021 13:20:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=posk.io; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=UqE0RmM7gK/dQ2NmLgZR9iia6oknN538MGKbbKe5kmg=; b=VfC/2KESGaQJhZx98qZ8Oj4GzCRSg2ul/EXyAsOT9ISi6hBNsL2QZLd29Sz0YkNpmQ 0YBDE+M6YHVNvIi0ZZ3Cj/zRzVsvGf+Vys4KOEw96zTFqb3Nz+tX09ak+jzdPS311HD2 6h6IwrdQo5L0b+rC6Wa3aAoIRfUlLy+UnSl1cscI3u2b/F9JNH6qsaaJzwZp6epMutwl Afqy+7/W/bS36wRJLDmL4UZBs6MatKhiuUj4BS1XN2kf5+jIAiuYg6A7cT7WL1NI0xYf pt/imOiogakgr0a2B7O8XrpmO9V/cm2/9xoPUPED73AopdedrngeWrmBFuRvSApKkxat t1AA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=UqE0RmM7gK/dQ2NmLgZR9iia6oknN538MGKbbKe5kmg=; b=tLb9privahFV2erWCvcdJyK8GDKkVBZl3hvlvmBfcUoqRgfCNYNwkUWNOAfJvpo1U7 IHVFmKuuuP0XmS+YWorChWIjlTr4cOADnPnuj8uKjLDmVZ7U8SwnL8Wt1bDGYmUDY2de P1O+4pe60sLStMzTwLT8TU20HzwaK48qadZDwQuuaFgnxby5xEaZKZG/XnihCRw0jDkx R/hP4NqxfqRssw6pIYHkDUzIBarvqN8E6CirTWGEQGxT4p40JtAfuXnutNBj2+KFpXX9 NK2bj9V7yDa5esPsZPWmoSprTOJdd0LMZFdQIHn4/zVwFj4LpSqcdhIEulnUn0df6fW+ HOYQ== X-Gm-Message-State: AOAM531IN2DeFB8uVv5zR6utvx0StqELuyG3X5P0kKpYciswf9WVxrMT rQNGvl5KoO+pw+7Q/b6U+WXx4w== X-Google-Smtp-Source: ABdhPJzl+7OeInZDP+uIq4cZqlN+tCWka/Xat9hKvRilfeB694CXKW6V/Om9i8wOj5ayuRPifae3og== X-Received: by 2002:a17:90b:1e07:: with SMTP id pg7mr23804710pjb.93.1637529645456; Sun, 21 Nov 2021 13:20:45 -0800 (PST) Received: from posk-p1g4.localdomain (23-118-52-46.lightspeed.sntcca.sbcglobal.net. [23.118.52.46]) by smtp.gmail.com with ESMTPSA id k8sm6207924pfu.75.2021.11.21.13.20.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 21 Nov 2021 13:20:45 -0800 (PST) From: Peter Oskolkov X-Google-Original-From: Peter Oskolkov To: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org Cc: Paul Turner , Ben Segall , Peter Oskolkov , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: [PATCH v0.9 1/6] sched/umcg: add WF_CURRENT_CPU and externise ttwu Date: Sun, 21 Nov 2021 13:20:35 -0800 Message-Id: <20211121212040.8649-2-posk@google.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211121212040.8649-1-posk@google.com> References: <20211121212040.8649-1-posk@google.com> MIME-Version: 1.0 X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 3CFE49001A92 X-Stat-Signature: yx6wih5xm5xb4s4ruwxgifgnriuk4st4 Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=posk.io header.s=google header.b="VfC/2KES"; spf=pass (imf29.hostedemail.com: domain of posk@posk.io designates 209.85.216.53 as permitted sender) smtp.mailfrom=posk@posk.io; dmarc=none X-HE-Tag: 1637529644-497267 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add WF_CURRENT_CPU wake flag that advices the scheduler to move the wakee to the current CPU. This is useful for fast on-CPU context switching use cases such as UMCG. In addition, make ttwu external rather than static so that the flag could be passed to it from outside of sched/core.c. Signed-off-by: Peter Oskolkov --- kernel/sched/core.c | 3 +-- kernel/sched/fair.c | 4 ++++ kernel/sched/sched.h | 15 +++++++++------ 3 files changed, 14 insertions(+), 8 deletions(-) -- 2.25.1 diff --git a/kernel/sched/core.c b/kernel/sched/core.c index beaa8be6241e..5344aa0afe5a 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -3977,8 +3977,7 @@ bool ttwu_state_match(struct task_struct *p, unsigned int state, int *success) * Return: %true if @p->state changes (an actual wakeup was done), * %false otherwise. */ -static int -try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) +int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { unsigned long flags; int cpu, success = 0; diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 884f29d07963..399422e6479b 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6890,6 +6890,10 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags) if (wake_flags & WF_TTWU) { record_wakee(p); + if ((wake_flags & WF_CURRENT_CPU) && + cpumask_test_cpu(cpu, p->cpus_ptr)) + return cpu; + if (sched_energy_enabled()) { new_cpu = find_energy_efficient_cpu(p, prev_cpu); if (new_cpu >= 0) diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index eb971151e7e4..5e1ecf89c12b 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -2052,13 +2052,14 @@ static inline int task_on_rq_migrating(struct task_struct *p) } /* Wake flags. The first three directly map to some SD flag value */ -#define WF_EXEC 0x02 /* Wakeup after exec; maps to SD_BALANCE_EXEC */ -#define WF_FORK 0x04 /* Wakeup after fork; maps to SD_BALANCE_FORK */ -#define WF_TTWU 0x08 /* Wakeup; maps to SD_BALANCE_WAKE */ +#define WF_EXEC 0x02 /* Wakeup after exec; maps to SD_BALANCE_EXEC */ +#define WF_FORK 0x04 /* Wakeup after fork; maps to SD_BALANCE_FORK */ +#define WF_TTWU 0x08 /* Wakeup; maps to SD_BALANCE_WAKE */ -#define WF_SYNC 0x10 /* Waker goes to sleep after wakeup */ -#define WF_MIGRATED 0x20 /* Internal use, task got migrated */ -#define WF_ON_CPU 0x40 /* Wakee is on_cpu */ +#define WF_SYNC 0x10 /* Waker goes to sleep after wakeup */ +#define WF_MIGRATED 0x20 /* Internal use, task got migrated */ +#define WF_ON_CPU 0x40 /* Wakee is on_cpu */ +#define WF_CURRENT_CPU 0x80 /* Prefer to move the wakee to the current CPU. */ #ifdef CONFIG_SMP static_assert(WF_EXEC == SD_BALANCE_EXEC); @@ -3076,6 +3077,8 @@ static inline bool is_per_cpu_kthread(struct task_struct *p) extern void swake_up_all_locked(struct swait_queue_head *q); extern void __prepare_to_swait(struct swait_queue_head *q, struct swait_queue *wait); +extern int try_to_wake_up(struct task_struct *tsk, unsigned int state, int wake_flags); + #ifdef CONFIG_PREEMPT_DYNAMIC extern int preempt_dynamic_mode; extern int sched_dynamic_mode(const char *str); From patchwork Sun Nov 21 21:20:36 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 12631063 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8F24DC433EF for ; Sun, 21 Nov 2021 21:22:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 972C66B0073; Sun, 21 Nov 2021 16:20:58 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 8FB3E6B0074; Sun, 21 Nov 2021 16:20:58 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 727016B0075; Sun, 21 Nov 2021 16:20:58 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0184.hostedemail.com [216.40.44.184]) by kanga.kvack.org (Postfix) with ESMTP id 6003E6B0073 for ; Sun, 21 Nov 2021 16:20:58 -0500 (EST) Received: from smtpin08.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 25D0F87CB0 for ; Sun, 21 Nov 2021 21:20:48 +0000 (UTC) X-FDA: 78834206976.08.DD1E0F3 Received: from mail-pg1-f174.google.com (mail-pg1-f174.google.com [209.85.215.174]) by imf16.hostedemail.com (Postfix) with ESMTP id D0B6CF000097 for ; Sun, 21 Nov 2021 21:20:44 +0000 (UTC) Received: by mail-pg1-f174.google.com with SMTP id l190so2999212pge.7 for ; Sun, 21 Nov 2021 13:20:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=posk.io; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=EBWkkjRPqMeXPNEjqt9BJ94U0PjT5H9NNNIQgB40MVM=; b=Bxlj+h1WWtgZPHn8smKfQrr0gJ4r+OdIOZBsTtBHGfzhIFdpLQ2Qctta8iMRGsScwB gt8tWd80Y/MFlqBXihPDKeW+VpAKym4PVNxto8Dxhw2Lzu67hV974nWAEhQeWuN4rHMg Qmm3PHXa1DgMEcIb3Aa8OvoPQUsNZQRRSWMZf1lMQF+9C8g5W6I+BYp2h/t+999twdUf 1PgYkRYBmt/hTuuXEdRlXZYUOwPlNzPALhDgAAtLdfVLUpAsjiKgImN+V4Fg1tqiE4FR zzuBxciZTyvc2tQdBhQtuhgjaCnOdSGJPMez9aQLt7qF0ob5wM4s4xn3JUbqrWcr/A3M GMyw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=EBWkkjRPqMeXPNEjqt9BJ94U0PjT5H9NNNIQgB40MVM=; b=BA6+0x2rA3c5DjVcvQ6bZs+9CrCXWEfvQLB37lN0w0d+zxzioIZsxGdVjc57dDtsxu rmlqKgRCegpgrx7ZsNSFKmhppTIBmnrGgZ8y79pKJfpSzp9NzvO9HFCEDrFUtF9hYl2e CXUGhRWhGL+WrzMwELFXJ5HTb3cO3LU82LbFCKgkvpTji+ZF+PGAmhqGA7X6SGA7HF8H L/NnbcPmLVIhmA4CZToETsvV3/Yqfb10gEwk9w1JCduQc+/mD552jTjKTjaOLDCtDwv/ sW5uiCC2tm6QeiIACPmuVP4dEqLqBgC71+y2RBm06XRLbhciqwiZSQIypt1ZjA9s6QnM WHnQ== X-Gm-Message-State: AOAM530aO6AglUlRq8aq6Hf5hCQmW6EGlUVAkzWdD0TSTl8AkHnfBNn1 ZK/Gk9VjlDGbhfTjjftcn6iFCw== X-Google-Smtp-Source: ABdhPJwHDZIwo8cZkZRlD5W40PQUgELOSQewc4+w94P2zFzALQicBs8lZPh/EqqUYywJze6hEA85YQ== X-Received: by 2002:a62:8c55:0:b0:49f:df22:c4ca with SMTP id m82-20020a628c55000000b0049fdf22c4camr81571686pfd.11.1637529646505; Sun, 21 Nov 2021 13:20:46 -0800 (PST) Received: from posk-p1g4.localdomain (23-118-52-46.lightspeed.sntcca.sbcglobal.net. [23.118.52.46]) by smtp.gmail.com with ESMTPSA id k8sm6207924pfu.75.2021.11.21.13.20.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 21 Nov 2021 13:20:46 -0800 (PST) From: Peter Oskolkov X-Google-Original-From: Peter Oskolkov To: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org Cc: Paul Turner , Ben Segall , Peter Oskolkov , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: [PATCH v0.9 2/6] mm, x86/uaccess: add userspace atomic helpers Date: Sun, 21 Nov 2021 13:20:36 -0800 Message-Id: <20211121212040.8649-3-posk@google.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211121212040.8649-1-posk@google.com> References: <20211121212040.8649-1-posk@google.com> MIME-Version: 1.0 X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: D0B6CF000097 X-Stat-Signature: 367cwyzop8pdn8hmb7yxhejhkr5s5pzr Authentication-Results: imf16.hostedemail.com; dkim=pass header.d=posk.io header.s=google header.b=Bxlj+h1W; spf=pass (imf16.hostedemail.com: domain of posk@posk.io designates 209.85.215.174 as permitted sender) smtp.mailfrom=posk@posk.io; dmarc=none X-HE-Tag: 1637529644-497486 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: In addition to futexes needing to do atomic operations in the userspace, a second use case is now in the works (UMCG, see https://lore.kernel.org/all/20210917180323.278250-1-posk@google.com/), so a generic facility to perform these operations has been called for (see https://lore.kernel.org/all/87ilyk9xc0.ffs@tglx/). Add a set of generic helpers to perform 32/64-bit xchg and cmpxchg operations in the userspace. Also implement the required architecture-specific support on x86_64. Signed-off-by: Peter Oskolkov Reported-by: kernel test robot --- arch/x86/include/asm/uaccess_64.h | 93 +++++++++++ include/linux/uaccess.h | 46 ++++++ mm/maccess.c | 264 ++++++++++++++++++++++++++++++ 3 files changed, 403 insertions(+) -- 2.25.1 diff --git a/arch/x86/include/asm/uaccess_64.h b/arch/x86/include/asm/uaccess_64.h index 45697e04d771..41e2f96d3ec4 100644 --- a/arch/x86/include/asm/uaccess_64.h +++ b/arch/x86/include/asm/uaccess_64.h @@ -79,4 +79,97 @@ __copy_from_user_flushcache(void *dst, const void __user *src, unsigned size) kasan_check_write(dst, size); return __copy_user_flushcache(dst, src, size); } + +#define ARCH_HAS_ATOMIC_UACCESS_HELPERS 1 + +static inline int __try_cmpxchg_user_32(u32 *uval, u32 __user *uaddr, + u32 oldval, u32 newval) +{ + int ret = 0; + + asm volatile("\n" + "1:\t" LOCK_PREFIX "cmpxchgl %4, %2\n" + "2:\n" + "\t.section .fixup, \"ax\"\n" + "3:\tmov %3, %0\n" + "\tjmp 2b\n" + "\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "+r" (ret), "=a" (oldval), "+m" (*uaddr) + : "i" (-EFAULT), "r" (newval), "1" (oldval) + : "memory" + ); + *uval = oldval; + return ret; +} + +static inline int __try_cmpxchg_user_64(u64 *uval, u64 __user *uaddr, + u64 oldval, u64 newval) +{ + int ret = 0; + + asm volatile("\n" + "1:\t" LOCK_PREFIX "cmpxchgq %4, %2\n" + "2:\n" + "\t.section .fixup, \"ax\"\n" + "3:\tmov %3, %0\n" + "\tjmp 2b\n" + "\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "+r" (ret), "=a" (oldval), "+m" (*uaddr) + : "i" (-EFAULT), "r" (newval), "1" (oldval) + : "memory" + ); + *uval = oldval; + return ret; +} + +static inline int __try_xchg_user_32(u32 *oval, u32 __user *uaddr, u32 newval) +{ + u32 oldval = 0; + int ret = 0; + + asm volatile("\n" + "1:\txchgl %0, %2\n" + "2:\n" + "\t.section .fixup, \"ax\"\n" + "3:\tmov %3, %1\n" + "\tjmp 2b\n" + "\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "=r" (oldval), "=r" (ret), "+m" (*uaddr) + : "i" (-EFAULT), "0" (newval), "1" (0) + ); + + if (ret) + return ret; + + *oval = oldval; + return 0; +} + +static inline int __try_xchg_user_64(u64 *oval, u64 __user *uaddr, u64 newval) +{ + u64 oldval = 0; + int ret = 0; + + asm volatile("\n" + "1:\txchgq %0, %2\n" + "2:\n" + "\t.section .fixup, \"ax\"\n" + "3:\tmov %3, %1\n" + "\tjmp 2b\n" + "\t.previous\n" + _ASM_EXTABLE_UA(1b, 3b) + : "=r" (oldval), "=r" (ret), "+m" (*uaddr) + : "i" (-EFAULT), "0" (newval), "1" (0) + ); + + if (ret) + return ret; + + *oval = oldval; + return 0; +} + #endif /* _ASM_X86_UACCESS_64_H */ diff --git a/include/linux/uaccess.h b/include/linux/uaccess.h index ac0394087f7d..dcb3ac093075 100644 --- a/include/linux/uaccess.h +++ b/include/linux/uaccess.h @@ -408,4 +408,50 @@ void __noreturn usercopy_abort(const char *name, const char *detail, unsigned long len); #endif +#ifdef ARCH_HAS_ATOMIC_UACCESS_HELPERS +/** + * cmpxchg_user_[32|64][_nofault|]() - compare_exchange 32/64-bit values + * @uaddr: Destination address, in user space; + * @curr_val: Source address, in kernel space; + * @new_val: The value to write to the destination address. + * + * This is the standard cmpxchg: atomically: compare *@uaddr to *@curr_val; + * if the values match, write @new_val to @uaddr, return 0; if the values + * do not match, write *@uaddr to @curr_val, return -EAGAIN. + * + * The _nofault versions don't fault and can be used in + * atomic/preempt-disabled contexts. + * + * Return: + * 0 : OK/success; + * -EINVAL: @uaddr is not properly aligned ('may fault' versions only); + * -EFAULT: memory access error (including mis-aligned @uaddr in _nofault); + * -EAGAIN: @old did not match. + */ +int cmpxchg_user_32_nofault(u32 __user *uaddr, u32 *curr_val, u32 new_val); +int cmpxchg_user_64_nofault(u64 __user *uaddr, u64 *curr_val, u64 new_val); +int cmpxchg_user_32(u32 __user *uaddr, u32 *curr_val, u32 new_val); +int cmpxchg_user_64(u64 __user *uaddr, u64 *curr_val, u64 new_val); + +/** + * xchg_user_[32|64][_nofault|]() - exchange 32/64-bit values + * @uaddr: Destination address, in user space; + * @val: Source address, in kernel space. + * + * This is the standard atomic xchg: exchange values pointed to by @uaddr and @val. + * + * The _nofault versions don't fault and can be used in + * atomic/preempt-disabled contexts. + * + * Return: + * 0 : OK/success; + * -EINVAL: @uaddr is not properly aligned ('may fault' versions only); + * -EFAULT: memory access error (including mis-aligned @uaddr in _nofault). + */ +int xchg_user_32_nofault(u32 __user *uaddr, u32 *val); +int xchg_user_64_nofault(u64 __user *uaddr, u64 *val); +int xchg_user_32(u32 __user *uaddr, u32 *val); +int xchg_user_64(u64 __user *uaddr, u64 *val); +#endif /* ARCH_HAS_ATOMIC_UACCESS_HELPERS */ + #endif /* __LINUX_UACCESS_H__ */ diff --git a/mm/maccess.c b/mm/maccess.c index d3f1a1f0b1c1..620556b11550 100644 --- a/mm/maccess.c +++ b/mm/maccess.c @@ -335,3 +335,267 @@ long strnlen_user_nofault(const void __user *unsafe_addr, long count) return ret; } + +#ifdef ARCH_HAS_ATOMIC_UACCESS_HELPERS + +static int fix_pagefault(unsigned long uaddr, bool write_fault, int bytes) +{ + struct mm_struct *mm = current->mm; + int ret; + + mmap_read_lock(mm); + ret = fixup_user_fault(mm, uaddr, write_fault ? FAULT_FLAG_WRITE : 0, + NULL); + mmap_read_unlock(mm); + + return ret < 0 ? ret : 0; +} + +int cmpxchg_user_32_nofault(u32 __user *uaddr, u32 *curr_val, u32 new_val) +{ + int ret = -EFAULT; + u32 __old = *curr_val; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + if (!user_access_begin(uaddr, sizeof(*uaddr))) { + pagefault_enable(); + return -EFAULT; + } + ret = __try_cmpxchg_user_32(curr_val, uaddr, __old, new_val); + user_access_end(); + + if (!ret) + ret = *curr_val == __old ? 0 : -EAGAIN; + + pagefault_enable(); + return ret; +} + +int cmpxchg_user_64_nofault(u64 __user *uaddr, u64 *curr_val, u64 new_val) +{ + int ret = -EFAULT; + u64 __old = *curr_val; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + if (!user_access_begin(uaddr, sizeof(*uaddr))) { + pagefault_enable(); + return -EFAULT; + } + ret = __try_cmpxchg_user_64(curr_val, uaddr, __old, new_val); + user_access_end(); + + if (!ret) + ret = *curr_val == __old ? 0 : -EAGAIN; + + pagefault_enable(); + + return ret; +} + +int cmpxchg_user_32(u32 __user *uaddr, u32 *curr_val, u32 new_val) +{ + int ret = -EFAULT; + u32 __old = *curr_val; + + /* Validate proper alignment. */ + if (unlikely(((unsigned long)uaddr % sizeof(*uaddr)) || + ((unsigned long)curr_val % sizeof(*curr_val)))) + return -EINVAL; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + while (true) { + ret = -EFAULT; + if (!user_access_begin(uaddr, sizeof(*uaddr))) + break; + + ret = __try_cmpxchg_user_32(curr_val, uaddr, __old, new_val); + user_access_end(); + + if (!ret) { + ret = *curr_val == __old ? 0 : -EAGAIN; + break; + } + + if (fix_pagefault((unsigned long)uaddr, true, sizeof(*uaddr)) < 0) + break; + } + + pagefault_enable(); + return ret; +} + +int cmpxchg_user_64(u64 __user *uaddr, u64 *curr_val, u64 new_val) +{ + int ret = -EFAULT; + u64 __old = *curr_val; + + /* Validate proper alignment. */ + if (unlikely(((unsigned long)uaddr % sizeof(*uaddr)) || + ((unsigned long)curr_val % sizeof(*curr_val)))) + return -EINVAL; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + while (true) { + ret = -EFAULT; + if (!user_access_begin(uaddr, sizeof(*uaddr))) + break; + + ret = __try_cmpxchg_user_64(curr_val, uaddr, __old, new_val); + user_access_end(); + + if (!ret) { + ret = *curr_val == __old ? 0 : -EAGAIN; + break; + } + + if (fix_pagefault((unsigned long)uaddr, true, sizeof(*uaddr)) < 0) + break; + } + + pagefault_enable(); + return ret; +} + +/** + * xchg_user_[32|64][_nofault|]() - exchange 32/64-bit values + * @uaddr: Destination address, in user space; + * @val: Source address, in kernel space. + * + * This is the standard atomic xchg: exchange values pointed to by @uaddr and @val. + * + * The _nofault versions don't fault and can be used in + * atomic/preempt-disabled contexts. + * + * Return: + * 0 : OK/success; + * -EINVAL: @uaddr is not properly aligned ('may fault' versions only); + * -EFAULT: memory access error (including mis-aligned @uaddr in _nofault). + */ +int xchg_user_32_nofault(u32 __user *uaddr, u32 *val) +{ + int ret; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + if (!user_access_begin(uaddr, sizeof(*uaddr))) { + pagefault_enable(); + return -EFAULT; + } + + ret = __try_xchg_user_32(val, uaddr, *val); + user_access_end(); + + pagefault_enable(); + + return ret; +} + +int xchg_user_64_nofault(u64 __user *uaddr, u64 *val) +{ + int ret; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + if (!user_access_begin(uaddr, sizeof(*uaddr))) { + pagefault_enable(); + return -EFAULT; + } + + ret = __try_xchg_user_64(val, uaddr, *val); + user_access_end(); + + pagefault_enable(); + + return ret; +} + +int xchg_user_32(u32 __user *uaddr, u32 *val) +{ + int ret = -EFAULT; + + /* Validate proper alignment. */ + if (unlikely(((unsigned long)uaddr % sizeof(*uaddr)) || + ((unsigned long)val % sizeof(*val)))) + return -EINVAL; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + while (true) { + ret = -EFAULT; + if (!user_access_begin(uaddr, sizeof(*uaddr))) + break; + + ret = __try_xchg_user_32(val, uaddr, *val); + user_access_end(); + + if (!ret) + break; + + if (fix_pagefault((unsigned long)uaddr, true, sizeof(*uaddr)) < 0) + break; + } + + pagefault_enable(); + + return ret; +} + +int xchg_user_64(u64 __user *uaddr, u64 *val) +{ + int ret = -EFAULT; + + /* Validate proper alignment. */ + if (unlikely(((unsigned long)uaddr % sizeof(*uaddr)) || + ((unsigned long)val % sizeof(*val)))) + return -EINVAL; + + if (unlikely(!access_ok(uaddr, sizeof(*uaddr)))) + return -EFAULT; + + pagefault_disable(); + + while (true) { + ret = -EFAULT; + if (!user_access_begin(uaddr, sizeof(*uaddr))) + break; + + ret = __try_xchg_user_64(val, uaddr, *val); + user_access_end(); + + if (!ret) + break; + + if (fix_pagefault((unsigned long)uaddr, true, sizeof(*uaddr)) < 0) + break; + } + + pagefault_enable(); + + return ret; +} +#endif /* ARCH_HAS_ATOMIC_UACCESS_HELPERS */ From patchwork Sun Nov 21 21:20:37 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 12631065 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 97F29C433F5 for ; Sun, 21 Nov 2021 21:22:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F3F296B0074; Sun, 21 Nov 2021 16:20:59 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id EC6F96B0075; Sun, 21 Nov 2021 16:20:59 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CA4D86B0078; Sun, 21 Nov 2021 16:20:59 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0204.hostedemail.com [216.40.44.204]) by kanga.kvack.org (Postfix) with ESMTP id B38186B0074 for ; Sun, 21 Nov 2021 16:20:59 -0500 (EST) Received: from smtpin12.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay04.hostedemail.com (Postfix) with ESMTP id 6EA8F89B5F for ; Sun, 21 Nov 2021 21:20:49 +0000 (UTC) X-FDA: 78834207018.12.2A80036 Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) by imf10.hostedemail.com (Postfix) with ESMTP id D8588600198E for ; Sun, 21 Nov 2021 21:20:46 +0000 (UTC) Received: by mail-pj1-f54.google.com with SMTP id w33-20020a17090a6ba400b001a722a06212so12110128pjj.0 for ; Sun, 21 Nov 2021 13:20:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=posk.io; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=PpbPETpFEBM/Kso/qgJFUiHSnY8ebGURsYhwYW9qkZ0=; b=gEwitA0Yyqcg1RwBAqScMxpPEgLAVuBxHyIGjkC+Pf/uPAF1X/NCrVHVsV6mxxMrVu 1euapNwILOK+3mTCagCDnUn3LiT3njkBf2yqSUi2GYvASUf9oy1zz1Yr0XTeI4FZANxv 4xVOAygPrOVog5m9HP9r8z4JRAciVmLfzOtOJZC2WN3dZLKLn2WEmi47PydvXGlgVKn/ 901IKYAZmwbt2T+4E1jdsrJV5sRNi+NipjJF1vpsuH2nDRmTV9pV52t1EQvEfK5by15t 7SJyRkJiTZRS9yh5AHbUEaEmwDnxb2lQfdo8bj60blZhahmiY6EInPfDoRAKz5JUvO+b ZePA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=PpbPETpFEBM/Kso/qgJFUiHSnY8ebGURsYhwYW9qkZ0=; b=mc5IkoTQV7x9bP87TVh6IAupQv4XwJ/XZ65Cknk0Lsy2ha+jpbaAbWTt526vhg1+SR kpifOowTeZmf8f4lHQ6mtDO1wxsTMbOWFEtPDyHV3f2WkR8TR5G5jEU7vm7zBFgFYKXZ Al33MOd78DzwbMWNrqOwiJo9KwCRaP+qsLyWVoIUfvMwiRjRAN1du7aB1V9CrWV7deSn wUWUyCDSpuAhXX1cyxB3ubRpaQKnqNSlH7rLQ43ODM5ZPt9igfWUDypoDEp1KuiBY+lY Mrj8vUKOki8oUjIoVmI+zV0eKa8p1bJJQS0wgBorlzR2IxJTPr9MtXYoJ+aqKyTFCT8/ JyRA== X-Gm-Message-State: AOAM5324eQRqhuiuISQP1g0JY4HxrwygEBg7zRCyT3k6V4iRKQotsqRv W4FviELcDWpu0Kvxswb1r1K9dg== X-Google-Smtp-Source: ABdhPJzbUtip77GKIk0u95C6aTCasCdXyDJSTFzkigT9szYkscOwMmaiwaBqQ289peXzwMM+xZ+vnA== X-Received: by 2002:a17:902:82c9:b0:142:401f:dc9 with SMTP id u9-20020a17090282c900b00142401f0dc9mr101935069plz.43.1637529647621; Sun, 21 Nov 2021 13:20:47 -0800 (PST) Received: from posk-p1g4.localdomain (23-118-52-46.lightspeed.sntcca.sbcglobal.net. [23.118.52.46]) by smtp.gmail.com with ESMTPSA id k8sm6207924pfu.75.2021.11.21.13.20.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 21 Nov 2021 13:20:47 -0800 (PST) From: Peter Oskolkov X-Google-Original-From: Peter Oskolkov To: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org Cc: Paul Turner , Ben Segall , Peter Oskolkov , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: [PATCH v0.9 3/6] sched/umcg: implement UMCG syscalls Date: Sun, 21 Nov 2021 13:20:37 -0800 Message-Id: <20211121212040.8649-4-posk@google.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211121212040.8649-1-posk@google.com> References: <20211121212040.8649-1-posk@google.com> MIME-Version: 1.0 X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: D8588600198E X-Stat-Signature: kjc3oc5kjsixhbt8gnob3bsauy4f14th Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=posk.io header.s=google header.b=gEwitA0Y; spf=pass (imf10.hostedemail.com: domain of posk@posk.io designates 209.85.216.54 as permitted sender) smtp.mailfrom=posk@posk.io; dmarc=none X-HE-Tag: 1637529646-730058 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Define struct umcg_task and two syscalls: sys_umcg_ctl sys_umcg_wait. User Managed Concurrency Groups is an M:N threading toolkit that allows constructing user space schedulers designed to efficiently manage heterogeneous in-process workloads while maintaining high CPU utilization (95%+). In addition, M:N threading and cooperative user space scheduling enables synchronous coding style and better cache locality when compared to asynchronous callback/continuation style of programming. UMCG kernel API is build around the following ideas: * UMCG server: a task/thread representing "kernel threads", or (v)CPUs; * UMCG worker: a task/thread representing "application threads", to be scheduled over servers; * UMCG task state: (NONE), RUNNING, BLOCKED, IDLE: states a UMCG task (a server or a worker) can be in; * UMCG task state flag: LOCKED, PREEMPTED: additional state flags that can be ORed with the task state to communicate additional information to the kernel; * struct umcg_task: a per-task userspace set of data fields, usually residing in the TLS, that fully reflects the current task's UMCG state and controls the way the kernel manages the task; * sys_umcg_ctl(): a syscall used to register the current task/thread as a server or a worker, or to unregister a UMCG task; * sys_umcg_wait(): a syscall used to put the current task to sleep and/or wake another task, pontentially context-switching between the two tasks on-CPU synchronously. In short, servers can be thought of as CPUs over which application threads (workers) are scheduled; at any one time a worker is either: - RUNNING: has a server and is schedulable by the kernel; - BLOCKED: blocked in the kernel (e.g. on I/O, or a futex); - IDLE: is not blocked, but cannot be scheduled by the kernel to run because it has no server assigned to it (e.g. because all available servers are busy "running" other workers). Usually the number of servers in a process is equal to the number of CPUs available to the kernel if the process is supposed to consume the whole machine, or less than the number of CPUs available if the process is sharing the machine with other workloads. The number of workers in a process can grow very large: tens of thousands is normal; hundreds of thousands and more (millions) is something that would be desirable to achieve in the future, as lightweight userspace threads in Java and Go easily scale to millions, and UMCG workers are (intended to be) conceptually similar to those. Detailed use cases and API behavior are provided in Documentation/userspace-api/umcg.txt (see sibling patches). Some high-level implementation notes: UMCG tasks (workers and servers) are "tagged" with struct umcg_task residing in userspace (usually in TLS) to facilitate kernel/userspace communication. This makes the kernel-side code much simpler (see e.g. the implementation of sys_umcg_wait), but also requires some careful uaccess handling and page pinning (see below). The main UMCG server/worker interaction looks like: a. worker W1 is RUNNING, with a server S attached to it sleeping in IDLE state; b. worker W1 blocks in the kernel, e.g. on I/O; c. the kernel marks W1 as BLOCKED, the attached server S as RUNNING, and wakes S (the "block detection" event); d. the server now picks another IDLE worker W2 to run: marks W2 as RUNNING, itself as IDLE, ands calls sys_umcg_wait(); e. when the blocking operation of W1 completes, the worker is marked by the kernel as IDLE and added to idle workers list (see struct umcg_task) for the userspace to pick up and later run (the "wake detection" event). While there are additional operations such as worker-to-worker context switch, preemption, workers "yielding", etc., the "workflow" above is the main worker/server interaction that drives the implementation. Specifically: - most operations are conceptually context switches: - scheduling a worker: a running server goes to sleep and "runs" a worker in its place; - block detection: worker is descheduled, and its server is woken; - wake detection: woken worker, running in the kernel, is descheduled, and if there is an idle server, it is woken to process the wake detection event; - to faciliate low scheduling latencies and cache locality, most server/worker interactions described above are performed synchronously "on CPU" via WF_CURRENT_CPU flag passed to ttwu; while at the moment the context switches are simulated by putting the switch-out task to sleep and waking the switch-into task on the same cpu, it is very much the long-term goal of this project to make the context switch much lighter, by tweaking runtime accounting and, maybe, even bypassing __schedule(); - worker blocking is detected in a hook to sched_submit_work; as mentioned above, the server is to be woken on the same CPU, synchronously; this code may not pagefault, so to access worker's and server's userspace memory (struct umcg_task), memory pages containing the worker's and the server's structs umcg_task are pinned when the worker is exiting to the userspace, and unpinned when the worker is descheduled; - worker wakeup is detected in a hook to sched_update_worker, and processed in the exit to usermode loop (via TIF_NOTIFY_RESUME); workers CAN pagefault on the wakeup path; - worker preemption is implemented by the userspace tagging the worker with UMCG_TF_PREEMPTED state flag and sending a NOOP signal to it; on the exit to usermode the worker is intercepted and its server is woken (see Documentation/userspace-api/umcg.txt for more details); - each state change is tagged with a unique timestamp (of MONOTONIC variety), so that - scheduling instrumentation is naturally available; - racing state changes are easily detected and ABA issues are avoided; see umcg_update_state() in umcg.c for implementation details, and Documentation/userspace-api/umcg.txt for a higher-level description. The previous version of the patchset can be found at https://lore.kernel.org/all/20211012232522.714898-1-posk@google.com/ containing some additional context and links to earlier discussions. More details are available in Documentation/userspace-api/umcg.txt in sibling patches, and in doc-comments in the code. Signed-off-by: Peter Oskolkov Reported-by: kernel test robot Reported-by: kernel test robot Reported-by: kernel test robot --- arch/x86/entry/syscalls/syscall_64.tbl | 2 + fs/exec.c | 1 + include/linux/sched.h | 71 ++ include/linux/syscalls.h | 3 + include/uapi/asm-generic/unistd.h | 7 +- include/uapi/linux/umcg.h | 137 ++++ init/Kconfig | 10 + kernel/entry/common.c | 4 +- kernel/exit.c | 5 + kernel/sched/Makefile | 1 + kernel/sched/core.c | 9 +- kernel/sched/umcg.c | 949 +++++++++++++++++++++++++ kernel/sys_ni.c | 4 + 13 files changed, 1199 insertions(+), 4 deletions(-) create mode 100644 include/uapi/linux/umcg.h create mode 100644 kernel/sched/umcg.c -- 2.25.1 diff --git a/arch/x86/entry/syscalls/syscall_64.tbl b/arch/x86/entry/syscalls/syscall_64.tbl index fe8f8dd157b4..f09f96bb7f35 100644 --- a/arch/x86/entry/syscalls/syscall_64.tbl +++ b/arch/x86/entry/syscalls/syscall_64.tbl @@ -371,6 +371,8 @@ 447 common memfd_secret sys_memfd_secret 448 common process_mrelease sys_process_mrelease 449 common futex_waitv sys_futex_waitv +450 common umcg_ctl sys_umcg_ctl +451 common umcg_wait sys_umcg_wait # # Due to a historical design error, certain syscalls are numbered differently diff --git a/fs/exec.c b/fs/exec.c index 537d92c41105..1749f0f74fed 100644 --- a/fs/exec.c +++ b/fs/exec.c @@ -1838,6 +1838,7 @@ static int bprm_execve(struct linux_binprm *bprm, current->fs->in_exec = 0; current->in_execve = 0; rseq_execve(current); + umcg_execve(current); acct_update_integrals(current); task_numa_free(current, false); return retval; diff --git a/include/linux/sched.h b/include/linux/sched.h index d2e261adb8ea..dc9a8b8c5761 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -67,6 +67,7 @@ struct sighand_struct; struct signal_struct; struct task_delay_info; struct task_group; +struct umcg_task; /* * Task state bitmask. NOTE! These bits are also @@ -1294,6 +1295,12 @@ struct task_struct { unsigned long rseq_event_mask; #endif +#ifdef CONFIG_UMCG + struct umcg_task __user *umcg_task; + struct page *pinned_umcg_worker_page; /* self */ + struct page *pinned_umcg_server_page; +#endif + struct tlbflush_unmap_batch tlb_ubc; union { @@ -1687,6 +1694,13 @@ extern struct pid *cad_pid; #define PF_KTHREAD 0x00200000 /* I am a kernel thread */ #define PF_RANDOMIZE 0x00400000 /* Randomize virtual address space */ #define PF_SWAPWRITE 0x00800000 /* Allowed to write to swap */ + +#ifdef CONFIG_UMCG +#define PF_UMCG_WORKER 0x01000000 /* UMCG worker */ +#else +#define PF_UMCG_WORKER 0x00000000 +#endif + #define PF_NO_SETAFFINITY 0x04000000 /* Userland is not allowed to meddle with cpus_mask */ #define PF_MCE_EARLY 0x08000000 /* Early kill for mce process policy */ #define PF_MEMALLOC_PIN 0x10000000 /* Allocation context constrained to zones which allow long term pinning. */ @@ -2287,6 +2301,63 @@ static inline void rseq_execve(struct task_struct *t) #endif +#ifdef CONFIG_UMCG + +void umcg_handle_resuming_worker(void); +void umcg_handle_exiting_worker(void); +void umcg_clear_child(struct task_struct *tsk); + +/* Called by bprm_execve() in fs/exec.c. */ +static inline void umcg_execve(struct task_struct *tsk) +{ + if (tsk->umcg_task) + umcg_clear_child(tsk); +} + +/* Called by exit_to_user_mode_loop() in kernel/entry/common.c.*/ +static inline void umcg_handle_notify_resume(void) +{ + if (current->flags & PF_UMCG_WORKER) + umcg_handle_resuming_worker(); +} + +/* Called by do_exit() in kernel/exit.c. */ +static inline void umcg_handle_exit(void) +{ + if (current->flags & PF_UMCG_WORKER) + umcg_handle_exiting_worker(); +} + +/* + * umcg_wq_worker_[sleeping|running] are called in core.c by + * sched_submit_work() and sched_update_worker(). + */ +void umcg_wq_worker_sleeping(struct task_struct *tsk); +void umcg_wq_worker_running(struct task_struct *tsk); + +#else /* CONFIG_UMCG */ + +static inline void umcg_clear_child(struct task_struct *tsk) +{ +} +static inline void umcg_execve(struct task_struct *tsk) +{ +} +static inline void umcg_handle_notify_resume(void) +{ +} +static inline void umcg_handle_exit(void) +{ +} +static inline void umcg_wq_worker_sleeping(struct task_struct *tsk) +{ +} +static inline void umcg_wq_worker_running(struct task_struct *tsk) +{ +} + +#endif + #ifdef CONFIG_DEBUG_RSEQ void rseq_syscall(struct pt_regs *regs); diff --git a/include/linux/syscalls.h b/include/linux/syscalls.h index 528a478dbda8..424a4686be74 100644 --- a/include/linux/syscalls.h +++ b/include/linux/syscalls.h @@ -72,6 +72,7 @@ struct open_how; struct mount_attr; struct landlock_ruleset_attr; enum landlock_rule_type; +struct umcg_task; #include #include @@ -1057,6 +1058,8 @@ asmlinkage long sys_landlock_add_rule(int ruleset_fd, enum landlock_rule_type ru const void __user *rule_attr, __u32 flags); asmlinkage long sys_landlock_restrict_self(int ruleset_fd, __u32 flags); asmlinkage long sys_memfd_secret(unsigned int flags); +asmlinkage long sys_umcg_ctl(u32 flags, struct umcg_task __user *self); +asmlinkage long sys_umcg_wait(u32 flags, u64 abs_timeout); /* * Architecture-specific system calls diff --git a/include/uapi/asm-generic/unistd.h b/include/uapi/asm-generic/unistd.h index 4557a8b6086f..6d29b3896d4c 100644 --- a/include/uapi/asm-generic/unistd.h +++ b/include/uapi/asm-generic/unistd.h @@ -883,8 +883,13 @@ __SYSCALL(__NR_process_mrelease, sys_process_mrelease) #define __NR_futex_waitv 449 __SYSCALL(__NR_futex_waitv, sys_futex_waitv) +#define __NR_umcg_ctl 450 +__SYSCALL(__NR_umcg_ctl, sys_umcg_ctl) +#define __NR_umcg_wait 451 +__SYSCALL(__NR_umcg_wait, sys_umcg_wait) #undef __NR_syscalls -#define __NR_syscalls 450 + +#define __NR_syscalls 452 /* * 32 bit systems traditionally used different diff --git a/include/uapi/linux/umcg.h b/include/uapi/linux/umcg.h new file mode 100644 index 000000000000..041027b429dd --- /dev/null +++ b/include/uapi/linux/umcg.h @@ -0,0 +1,137 @@ +/* SPDX-License-Identifier: GPL-2.0+ WITH Linux-syscall-note */ +#ifndef _UAPI_LINUX_UMCG_H +#define _UAPI_LINUX_UMCG_H + +#include +#include + +/* + * UMCG: User Managed Concurrency Groups. + * + * Syscalls (see kernel/sched/umcg.c): + * sys_umcg_ctl() - register/unregister UMCG tasks; + * sys_umcg_wait() - wait/wake/context-switch. + * + * struct umcg_task (below): controls the state of UMCG tasks. + * + * See Documentation/userspace-api/umcg.txt for detals. + */ + +/* + * UMCG task states, the first 6 bits of struct umcg_task.state_ts. + * The states represent the user space point of view. + */ +#define UMCG_TASK_NONE 0ULL +#define UMCG_TASK_RUNNING 1ULL +#define UMCG_TASK_IDLE 2ULL +#define UMCG_TASK_BLOCKED 3ULL + +/* UMCG task state flags, bits 7-8 */ + +/* + * UMCG_TF_LOCKED: locked by the userspace in preparation to calling umcg_wait. + */ +#define UMCG_TF_LOCKED (1ULL << 6) + +/* + * UMCG_TF_PREEMPTED: the userspace indicates the worker should be preempted. + */ +#define UMCG_TF_PREEMPTED (1ULL << 7) + +/* The first six bits: RUNNING, IDLE, or BLOCKED. */ +#define UMCG_TASK_STATE_MASK 0x3fULL + +/* The full state mask: the first 18 bits. */ +#define UMCG_TASK_STATE_MASK_FULL 0x3ffffULL + +/* + * The number of bits reserved for UMCG state timestamp in + * struct umcg_task.state_ts. + */ +#define UMCG_STATE_TIMESTAMP_BITS 46 + +/* The number of bits truncated from UMCG state timestamp. */ +#define UMCG_STATE_TIMESTAMP_GRANULARITY 4 + +/** + * struct umcg_task - controls the state of UMCG tasks. + * + * The struct is aligned at 64 bytes to ensure that it fits into + * a single cache line. + */ +struct umcg_task { + /** + * @state_ts: the current state of the UMCG task described by + * this struct, with a unique timestamp indicating + * when the last state change happened. + * + * Readable/writable by both the kernel and the userspace. + * + * UMCG task state: + * bits 0 - 5: task state; + * bits 6 - 7: state flags; + * bits 8 - 12: reserved; must be zeroes; + * bits 13 - 17: for userspace use; + * bits 18 - 63: timestamp (see below). + * + * Timestamp: a 46-bit CLOCK_MONOTONIC timestamp, at 16ns resolution. + * See Documentation/userspace-api/umcg.txt for detals. + */ + u64 state_ts; /* r/w */ + + /** + * @next_tid: the TID of the UMCG task that should be context-switched + * into in sys_umcg_wait(). Can be zero. + * + * Running UMCG workers must have next_tid set to point to IDLE + * UMCG servers. + * + * Read-only for the kernel, read/write for the userspace. + */ + u32 next_tid; /* r */ + + u32 flags; /* Reserved; must be zero. */ + + /** + * @idle_workers_ptr: a single-linked list of idle workers. Can be NULL. + * + * Readable/writable by both the kernel and the userspace: the + * kernel adds items to the list, the userspace removes them. + */ + u64 idle_workers_ptr; /* r/w */ + + /** + * @idle_server_tid_ptr: a pointer pointing to a single idle server. + * Readonly. + */ + u64 idle_server_tid_ptr; /* r */ +} __attribute__((packed, aligned(8 * sizeof(__u64)))); + +/** + * enum umcg_ctl_flag - flags to pass to sys_umcg_ctl + * @UMCG_CTL_REGISTER: register the current task as a UMCG task + * @UMCG_CTL_UNREGISTER: unregister the current task as a UMCG task + * @UMCG_CTL_WORKER: register the current task as a UMCG worker + */ +enum umcg_ctl_flag { + UMCG_CTL_REGISTER = 0x00001, + UMCG_CTL_UNREGISTER = 0x00002, + UMCG_CTL_WORKER = 0x10000, +}; + +/** + * enum umcg_wait_flag - flags to pass to sys_umcg_wait + * @UMCG_WAIT_WAKE_ONLY: wake @self->next_tid, don't put @self to sleep; + * @UMCG_WAIT_WF_CURRENT_CPU: wake @self->next_tid on the current CPU + * (use WF_CURRENT_CPU); @UMCG_WAIT_WAKE_ONLY + * must be set. + */ +enum umcg_wait_flag { + UMCG_WAIT_WAKE_ONLY = 1, + UMCG_WAIT_WF_CURRENT_CPU = 2, +}; + +/* See Documentation/userspace-api/umcg.txt.*/ +#define UMCG_IDLE_NODE_PENDING (1ULL) + +#endif /* _UAPI_LINUX_UMCG_H */ diff --git a/init/Kconfig b/init/Kconfig index 036b750e8d8a..365802b25100 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1693,6 +1693,16 @@ config MEMBARRIER If unsure, say Y. +config UMCG + bool "Enable User Managed Concurrency Groups API" + depends on X86_64 + default n + help + Enable User Managed Concurrency Groups API, which form the basis + for an in-process M:N userspace scheduling framework. + At the moment this is an experimental/RFC feature that is not + guaranteed to be backward-compatible. + config KALLSYMS bool "Load all symbols for debugging/ksymoops" if EXPERT default y diff --git a/kernel/entry/common.c b/kernel/entry/common.c index d5a61d565ad5..62453772a0c7 100644 --- a/kernel/entry/common.c +++ b/kernel/entry/common.c @@ -171,8 +171,10 @@ static unsigned long exit_to_user_mode_loop(struct pt_regs *regs, if (ti_work & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL)) handle_signal_work(regs, ti_work); - if (ti_work & _TIF_NOTIFY_RESUME) + if (ti_work & _TIF_NOTIFY_RESUME) { + umcg_handle_notify_resume(); tracehook_notify_resume(regs); + } /* Architecture specific TIF work */ arch_exit_to_user_mode_work(regs, ti_work); diff --git a/kernel/exit.c b/kernel/exit.c index f702a6a63686..4bdd51c75aee 100644 --- a/kernel/exit.c +++ b/kernel/exit.c @@ -749,6 +749,10 @@ void __noreturn do_exit(long code) if (unlikely(!tsk->pid)) panic("Attempted to kill the idle task!"); + /* Turn off UMCG sched hooks. */ + if (unlikely(tsk->flags & PF_UMCG_WORKER)) + tsk->flags &= ~PF_UMCG_WORKER; + /* * If do_exit is called because this processes oopsed, it's possible * that get_fs() was left as KERNEL_DS, so reset it to USER_DS before @@ -786,6 +790,7 @@ void __noreturn do_exit(long code) io_uring_files_cancel(); exit_signals(tsk); /* sets PF_EXITING */ + umcg_handle_exit(); /* sync mm's RSS info before statistics gathering */ if (tsk->mm) diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile index c7421f2d05e1..c03eea9bc738 100644 --- a/kernel/sched/Makefile +++ b/kernel/sched/Makefile @@ -41,3 +41,4 @@ obj-$(CONFIG_MEMBARRIER) += membarrier.o obj-$(CONFIG_CPU_ISOLATION) += isolation.o obj-$(CONFIG_PSI) += psi.o obj-$(CONFIG_SCHED_CORE) += core_sched.o +obj-$(CONFIG_UMCG) += umcg.o diff --git a/kernel/sched/core.c b/kernel/sched/core.c index 5344aa0afe5a..26362cfcee84 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -4269,6 +4269,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p) p->wake_entry.u_flags = CSD_TYPE_TTWU; p->migration_pending = NULL; #endif + umcg_clear_child(p); } DEFINE_STATIC_KEY_FALSE(sched_numa_balancing); @@ -6327,9 +6328,11 @@ static inline void sched_submit_work(struct task_struct *tsk) * If a worker goes to sleep, notify and ask workqueue whether it * wants to wake up a task to maintain concurrency. */ - if (task_flags & (PF_WQ_WORKER | PF_IO_WORKER)) { + if (task_flags & (PF_WQ_WORKER | PF_IO_WORKER | PF_UMCG_WORKER)) { if (task_flags & PF_WQ_WORKER) wq_worker_sleeping(tsk); + else if (task_flags & PF_UMCG_WORKER) + umcg_wq_worker_sleeping(tsk); else io_wq_worker_sleeping(tsk); } @@ -6347,9 +6350,11 @@ static inline void sched_submit_work(struct task_struct *tsk) static void sched_update_worker(struct task_struct *tsk) { - if (tsk->flags & (PF_WQ_WORKER | PF_IO_WORKER)) { + if (tsk->flags & (PF_WQ_WORKER | PF_IO_WORKER | PF_UMCG_WORKER)) { if (tsk->flags & PF_WQ_WORKER) wq_worker_running(tsk); + else if (tsk->flags & PF_UMCG_WORKER) + umcg_wq_worker_running(tsk); else io_wq_worker_running(tsk); } diff --git a/kernel/sched/umcg.c b/kernel/sched/umcg.c new file mode 100644 index 000000000000..0851cdc2eddc --- /dev/null +++ b/kernel/sched/umcg.c @@ -0,0 +1,949 @@ +// SPDX-License-Identifier: GPL-2.0-only + +/* + * User Managed Concurrency Groups (UMCG). + * + * See Documentation/userspace-api/umcg.txt for detals. + */ + +#include +#include +#include +#include + +#include "sched.h" + +/** + * get_user_nofault - get user value without sleeping. + * + * get_user() might sleep and therefore cannot be used in preempt-disabled + * regions. + */ +#define get_user_nofault(out, uaddr) \ +({ \ + int ret = -EFAULT; \ + \ + if (access_ok((uaddr), sizeof(*(uaddr)))) { \ + pagefault_disable(); \ + \ + if (!__get_user((out), (uaddr))) \ + ret = 0; \ + \ + pagefault_enable(); \ + } \ + ret; \ +}) + +/** + * umcg_pin_pages: pin pages containing struct umcg_task of this worker + * and its server. + * + * The pages are pinned when the worker exits to the userspace and unpinned + * when the worker is in sched_submit_work(), i.e. when the worker is + * about to be removed from its runqueue. Thus at most NR_CPUS UMCG pages + * are pinned at any one time across the whole system. + * + * The pinning is needed so that going-to-sleep workers can access + * their and their servers' userspace umcg_task structs without page faults, + * as the code path can be executed in the context of a pagefault, with + * mm lock held. + */ +static int umcg_pin_pages(u32 server_tid) +{ + struct umcg_task __user *worker_ut = current->umcg_task; + struct umcg_task __user *server_ut = NULL; + struct task_struct *tsk; + + rcu_read_lock(); + tsk = find_task_by_vpid(server_tid); + /* Server/worker interaction is allowed only within the same mm. */ + if (tsk && current->mm == tsk->mm) + server_ut = READ_ONCE(tsk->umcg_task); + rcu_read_unlock(); + + if (!server_ut) + return -EINVAL; + + tsk = current; + + /* worker_ut is stable, don't need to repin */ + if (!tsk->pinned_umcg_worker_page) + if (1 != pin_user_pages_fast((unsigned long)worker_ut, 1, 0, + &tsk->pinned_umcg_worker_page)) + return -EFAULT; + + /* server_ut may change, need to repin */ + if (tsk->pinned_umcg_server_page) { + unpin_user_page(tsk->pinned_umcg_server_page); + tsk->pinned_umcg_server_page = NULL; + } + + if (1 != pin_user_pages_fast((unsigned long)server_ut, 1, 0, + &tsk->pinned_umcg_server_page)) + return -EFAULT; + + return 0; +} + +static void umcg_unpin_pages(void) +{ + struct task_struct *tsk = current; + + if (tsk->pinned_umcg_worker_page) + unpin_user_page(tsk->pinned_umcg_worker_page); + if (tsk->pinned_umcg_server_page) + unpin_user_page(tsk->pinned_umcg_server_page); + + tsk->pinned_umcg_worker_page = NULL; + tsk->pinned_umcg_server_page = NULL; +} + +static void umcg_clear_task(struct task_struct *tsk) +{ + /* + * This is either called for the current task, or for a newly forked + * task that is not yet running, so we don't need strict atomicity + * below. + */ + if (tsk->umcg_task) { + WRITE_ONCE(tsk->umcg_task, NULL); + + /* These can be simple writes - see the commment above. */ + tsk->pinned_umcg_worker_page = NULL; + tsk->pinned_umcg_server_page = NULL; + tsk->flags &= ~PF_UMCG_WORKER; + } +} + +/* Called for a forked or execve-ed child. */ +void umcg_clear_child(struct task_struct *tsk) +{ + umcg_clear_task(tsk); +} + +/* Called both by normally (unregister) and abnormally exiting workers. */ +void umcg_handle_exiting_worker(void) +{ + umcg_unpin_pages(); + umcg_clear_task(current); +} + +/** + * umcg_update_state: atomically update umcg_task.state_ts, set new timestamp. + * @state_ts - points to the state_ts member of struct umcg_task to update; + * @expected - the expected value of state_ts, including the timestamp; + * @desired - the desired value of state_ts, state part only; + * @may_fault - whether to use normal or _nofault cmpxchg. + * + * The function is basically cmpxchg(state_ts, expected, desired), with extra + * code to set the timestamp in @desired. + */ +static int umcg_update_state(u64 __user *state_ts, u64 *expected, u64 desired, + bool may_fault) +{ + u64 curr_ts = (*expected) >> (64 - UMCG_STATE_TIMESTAMP_BITS); + u64 next_ts = ktime_get_ns() >> UMCG_STATE_TIMESTAMP_GRANULARITY; + + /* Cut higher order bits. */ + next_ts &= (1 << UMCG_STATE_TIMESTAMP_BITS) - 1; + + if (next_ts == curr_ts) + ++next_ts; + + /* Remove an old timestamp, if any. */ + desired &= UMCG_TASK_STATE_MASK_FULL; + + /* Set the new timestamp. */ + desired |= (next_ts << (64 - UMCG_STATE_TIMESTAMP_BITS)); + + if (may_fault) + return cmpxchg_user_64(state_ts, expected, desired); + + return cmpxchg_user_64_nofault(state_ts, expected, desired); +} + +/** + * sys_umcg_ctl: (un)register the current task as a UMCG task. + * @flags: ORed values from enum umcg_ctl_flag; see below; + * @self: a pointer to struct umcg_task that describes this + * task and governs the behavior of sys_umcg_wait if + * registering; must be NULL if unregistering. + * + * @flags & UMCG_CTL_REGISTER: register a UMCG task: + * UMCG workers: + * - @flags & UMCG_CTL_WORKER + * - self->state must be UMCG_TASK_BLOCKED + * UMCG servers: + * - !(@flags & UMCG_CTL_WORKER) + * - self->state must be UMCG_TASK_RUNNING + * + * All tasks: + * - self->next_tid must be zero + * + * If the conditions above are met, sys_umcg_ctl() immediately returns + * if the registered task is a server; a worker will be added to + * idle_workers_ptr, and the worker put to sleep; an idle server + * from idle_server_tid_ptr will be woken, if present. + * + * @flags == UMCG_CTL_UNREGISTER: unregister a UMCG task. If the current task + * is a UMCG worker, the userspace is responsible for waking its + * server (before or after calling sys_umcg_ctl). + * + * Return: + * 0 - success + * -EFAULT - failed to read @self + * -EINVAL - some other error occurred + */ +SYSCALL_DEFINE2(umcg_ctl, u32, flags, struct umcg_task __user *, self) +{ + struct umcg_task ut; + + if (flags == UMCG_CTL_UNREGISTER) { + if (self || !current->umcg_task) + return -EINVAL; + + if (current->flags & PF_UMCG_WORKER) + umcg_handle_exiting_worker(); + else + umcg_clear_task(current); + + return 0; + } + + if (!(flags & UMCG_CTL_REGISTER)) + return -EINVAL; + + flags &= ~UMCG_CTL_REGISTER; + if (flags && flags != UMCG_CTL_WORKER) + return -EINVAL; + + if (current->umcg_task || !self) + return -EINVAL; + + if (copy_from_user(&ut, self, sizeof(ut))) + return -EFAULT; + + if (ut.next_tid) + return -EINVAL; + + if (flags == UMCG_CTL_WORKER) { + if ((ut.state_ts & UMCG_TASK_STATE_MASK_FULL) != UMCG_TASK_BLOCKED) + return -EINVAL; + + WRITE_ONCE(current->umcg_task, self); + current->flags |= PF_UMCG_WORKER; + + /* Trigger umcg_handle_resuming_worker() */ + set_tsk_thread_flag(current, TIF_NOTIFY_RESUME); + } else { + if ((ut.state_ts & UMCG_TASK_STATE_MASK_FULL) != UMCG_TASK_RUNNING) + return -EINVAL; + + WRITE_ONCE(current->umcg_task, self); + } + + return 0; +} + +/** + * handle_timedout_worker - make sure the worker is added to idle_workers + * upon a "clean" timeout. + */ +static int handle_timedout_worker(struct umcg_task __user *self) +{ + u64 curr_state, next_state; + int ret; + + if (get_user(curr_state, &self->state_ts)) + return -EFAULT; + + if ((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_IDLE) { + /* TODO: should we care here about TF_LOCKED or TF_PREEMPTED? */ + + next_state = curr_state & ~UMCG_TASK_STATE_MASK; + next_state |= UMCG_TASK_BLOCKED; + + ret = umcg_update_state(&self->state_ts, &curr_state, next_state, true); + if (ret) + return ret; + + return -ETIMEDOUT; + } + + return 0; /* Not really timed out. */ +} + +/* + * umcg_should_idle - return true if tasks with @state should block in + * imcg_idle_loop(). + */ +static bool umcg_should_idle(u64 state) +{ + switch (state & UMCG_TASK_STATE_MASK) { + case UMCG_TASK_RUNNING: + return state & UMCG_TF_LOCKED; + case UMCG_TASK_IDLE: + return !(state & UMCG_TF_LOCKED); + case UMCG_TASK_BLOCKED: + return false; + default: + WARN_ONCE(true, "unknown UMCG task state"); + return false; + } +} + +/** + * umcg_idle_loop - sleep until !umcg_should_idle() or a timeout expires + * @abs_timeout - absolute timeout in nanoseconds; zero => no timeout + * + * The function marks the current task as INTERRUPTIBLE and calls + * freezable_schedule(). + * + * Note: because UMCG workers should not be running WITHOUT attached servers, + * and because servers should not be running WITH attached workers, + * the function returns only on fatal signal pending and ignores/flushes + * all other signals. + */ +static int umcg_idle_loop(u64 abs_timeout) +{ + int ret; + struct page *pinned_page = NULL; + struct hrtimer_sleeper timeout; + struct umcg_task __user *self = current->umcg_task; + const bool worker = current->flags & PF_UMCG_WORKER; + + /* Clear PF_UMCG_WORKER to elide workqueue handlers. */ + if (worker) + current->flags &= ~PF_UMCG_WORKER; + + if (abs_timeout) { + hrtimer_init_sleeper_on_stack(&timeout, CLOCK_REALTIME, + HRTIMER_MODE_ABS); + + hrtimer_set_expires_range_ns(&timeout.timer, (s64)abs_timeout, + current->timer_slack_ns); + } + + while (true) { + u64 umcg_state; + + /* + * We need to read from userspace _after_ the task is marked + * TASK_INTERRUPTIBLE, to properly handle concurrent wakeups; + * but faulting is not allowed; so we try a fast no-fault read, + * and if it fails, pin the page temporarily. + */ +retry_once: + set_current_state(TASK_INTERRUPTIBLE); + + /* Order set_current_state above with get_user below. */ + smp_mb(); + ret = -EFAULT; + if (get_user_nofault(umcg_state, &self->state_ts)) { + set_current_state(TASK_RUNNING); + + if (pinned_page) + goto out; + else if (1 != pin_user_pages_fast((unsigned long)self, + 1, 0, &pinned_page)) + goto out; + + goto retry_once; + } + + if (pinned_page) { + unpin_user_page(pinned_page); + pinned_page = NULL; + } + + ret = 0; + if (!umcg_should_idle(umcg_state)) { + set_current_state(TASK_RUNNING); + goto out; + } + + if (abs_timeout) + hrtimer_sleeper_start_expires(&timeout, HRTIMER_MODE_ABS); + + if (!abs_timeout || timeout.task) + freezable_schedule(); + + __set_current_state(TASK_RUNNING); + + /* + * Check for timeout before checking the state, as workers + * are not going to return from freezable_schedule() unless + * they are RUNNING. + */ + ret = -ETIMEDOUT; + if (abs_timeout && !timeout.task) + goto out; + + /* Order set_current_state above with get_user below. */ + smp_mb(); + ret = -EFAULT; + if (get_user(umcg_state, &self->state_ts)) + goto out; + + ret = 0; + if (!umcg_should_idle(umcg_state)) + goto out; + + ret = -EINTR; + if (fatal_signal_pending(current)) + goto out; + + if (signal_pending(current)) + flush_signals(current); + } + +out: + if (pinned_page) { + unpin_user_page(pinned_page); + pinned_page = NULL; + } + if (abs_timeout) { + hrtimer_cancel(&timeout.timer); + destroy_hrtimer_on_stack(&timeout.timer); + } + if (worker) { + current->flags |= PF_UMCG_WORKER; + + if (ret == -ETIMEDOUT) + ret = handle_timedout_worker(self); + + /* Workers must go through workqueue handlers upon wakeup. */ + set_tsk_thread_flag(current, TIF_NOTIFY_RESUME); + } + return ret; +} + +/** + * umcg_wakeup_allowed - check whether @current can wake @tsk. + * + * Currently a placeholder that allows wakeups within a single process + * only (same mm). In the future the requirement will be relaxed (securely). + */ +static bool umcg_wakeup_allowed(struct task_struct *tsk) +{ + WARN_ON_ONCE(!rcu_read_lock_held()); + + if (tsk->mm && tsk->mm == current->mm && READ_ONCE(tsk->umcg_task)) + return true; + + return false; +} + +/* + * Try to wake up. May be called with preempt_disable set. May be called + * cross-process. + * + * Note: umcg_ttwu succeeds even if ttwu fails: see wait/wake state + * ordering logic. + */ +static int umcg_ttwu(u32 next_tid, int wake_flags) +{ + struct task_struct *next; + + rcu_read_lock(); + next = find_task_by_vpid(next_tid); + if (!next || !umcg_wakeup_allowed(next)) { + rcu_read_unlock(); + return -ESRCH; + } + + /* The result of ttwu below is ignored. */ + try_to_wake_up(next, TASK_NORMAL, wake_flags); + rcu_read_unlock(); + + return 0; +} + +/* + * At the moment, umcg_do_context_switch simply wakes up @next with + * WF_CURRENT_CPU and puts the current task to sleep. + * + * In the future an optimization will be added to adjust runtime accounting + * so that from the kernel scheduling perspective the two tasks are + * essentially treated as one. In addition, the context switch may be performed + * right here on the fast path, instead of going through the wake/wait pair. + */ +static int umcg_do_context_switch(u32 next_tid, u64 abs_timeout) +{ + int ret; + + ret = umcg_ttwu(next_tid, WF_CURRENT_CPU); + if (ret) + return ret; + + return umcg_idle_loop(abs_timeout); +} + +/** + * sys_umcg_wait: put the current task to sleep and/or wake another task. + * @flags: zero or a value from enum umcg_wait_flag. + * @abs_timeout: when to wake the task, in nanoseconds; zero for no timeout. + * + * @self->state_ts must be UMCG_TASK_IDLE (where @self is current->umcg_task) + * if !(@flags & UMCG_WAIT_WAKE_ONLY) (also see umcg_idle_loop and + * umcg_should_idle above). + * + * If @self->next_tid is not zero, it must point to an IDLE UMCG task. + * The userspace must have changed its state from IDLE to RUNNING + * before calling sys_umcg_wait() in the current task. This "next" + * task will be woken (context-switched-to on the fast path) when the + * current task is put to sleep. + * + * See Documentation/userspace-api/umcg.txt for detals. + * + * Return: + * 0 - OK; + * -ETIMEDOUT - the timeout expired; + * -EFAULT - failed accessing struct umcg_task __user of the current + * task; + * -ESRCH - the task to wake not found or not a UMCG task; + * -EINVAL - another error happened (e.g. bad @flags, or the current + * task is not a UMCG task, etc.) + */ +SYSCALL_DEFINE2(umcg_wait, u32, flags, u64, abs_timeout) +{ + struct umcg_task __user *self = current->umcg_task; + u32 next_tid; + + if (!self) + return -EINVAL; + + if (get_user(next_tid, &self->next_tid)) + return -EFAULT; + + if (flags & UMCG_WAIT_WAKE_ONLY) { + if (!next_tid || abs_timeout) + return -EINVAL; + + flags &= ~UMCG_WAIT_WAKE_ONLY; + if (flags & ~UMCG_WAIT_WF_CURRENT_CPU) + return -EINVAL; + + return umcg_ttwu(next_tid, flags & UMCG_WAIT_WF_CURRENT_CPU ? + WF_CURRENT_CPU : 0); + } + + /* Unlock the worker, if locked. */ + if (current->flags & PF_UMCG_WORKER) { + u64 umcg_state; + + if (get_user(umcg_state, &self->state_ts)) + return -EFAULT; + + if ((umcg_state & UMCG_TF_LOCKED) && umcg_update_state( + &self->state_ts, &umcg_state, + umcg_state & ~UMCG_TF_LOCKED, true)) + return -EFAULT; + } + + if (next_tid) + return umcg_do_context_switch(next_tid, abs_timeout); + + return umcg_idle_loop(abs_timeout); +} + +/* + * NOTE: all code below is called from workqueue submit/update, or + * syscall exit to usermode loop, so all errors result in the + * termination of the current task (via SIGKILL). + */ + +/* + * Wake idle server: find the task, change its state IDLE=>RUNNING, ttwu. + */ +static int umcg_wake_idle_server_nofault(u32 server_tid) +{ + struct umcg_task __user *ut_server = NULL; + struct task_struct *tsk; + int ret = -EINVAL; + u64 state; + + rcu_read_lock(); + + tsk = find_task_by_vpid(server_tid); + /* Server/worker interaction is allowed only within the same mm. */ + if (tsk && current->mm == tsk->mm) + ut_server = READ_ONCE(tsk->umcg_task); + + if (!ut_server) + goto out_rcu; + + ret = -EFAULT; + if (get_user_nofault(state, &ut_server->state_ts)) + goto out_rcu; + + ret = -EAGAIN; + if ((state & UMCG_TASK_STATE_MASK) != UMCG_TASK_IDLE) + goto out_rcu; + + ret = umcg_update_state(&ut_server->state_ts, &state, + (state & ~UMCG_TASK_STATE_MASK) | UMCG_TASK_RUNNING, + false); + + if (ret) + goto out_rcu; + + try_to_wake_up(tsk, TASK_NORMAL, WF_CURRENT_CPU); + +out_rcu: + rcu_read_unlock(); + return ret; +} + +/* + * Wake idle server: find the task, change its state IDLE=>RUNNING, ttwu. + */ +static int umcg_wake_idle_server_may_fault(u32 server_tid) +{ + struct umcg_task __user *ut_server = NULL; + struct task_struct *tsk; + int ret = -EINVAL; + u64 state; + + rcu_read_lock(); + tsk = find_task_by_vpid(server_tid); + if (tsk && current->mm == tsk->mm) + ut_server = READ_ONCE(tsk->umcg_task); + rcu_read_unlock(); + + if (!ut_server) + return -EINVAL; + + if (get_user(state, &ut_server->state_ts)) + return -EFAULT; + + if ((state & UMCG_TASK_STATE_MASK) != UMCG_TASK_IDLE) + return -EAGAIN; + + ret = umcg_update_state(&ut_server->state_ts, &state, + (state & ~UMCG_TASK_STATE_MASK) | UMCG_TASK_RUNNING, + true); + if (ret) + return ret; + + /* + * umcg_ttwu will call find_task_by_vpid again; but we cannot + * elide this, as we cannot do get_user() from an rcu-locked + * code block. + */ + return umcg_ttwu(server_tid, WF_CURRENT_CPU); +} + +/* + * Wake idle server: find the task, change its state IDLE=>RUNNING, ttwu. + */ +static int umcg_wake_idle_server(u32 server_tid, bool may_fault) +{ + int ret = umcg_wake_idle_server_nofault(server_tid); + + if (!ret) + return 0; + + if (!may_fault || ret != -EFAULT) + return ret; + + return umcg_wake_idle_server_may_fault(server_tid); +} + +/* + * Called in sched_submit_work() context for UMCG workers. In the common case, + * the worker's state changes RUNNING => BLOCKED, and its server's state + * changes IDLE => RUNNING, and the server is ttwu-ed. + * + * Under some conditions (e.g. the worker is "locked", see + * /Documentation/userspace-api/umcg.txt for more details), the + * function does nothing. + * + * The function is called with preempt disabled to make sure the retry_once + * logic below works correctly. + */ +static void process_sleeping_worker(struct task_struct *tsk, u32 *server_tid) +{ + struct umcg_task __user *ut_worker = tsk->umcg_task; + u64 curr_state, next_state; + bool retried = false; + u32 tid; + int ret; + + *server_tid = 0; + + if (WARN_ONCE((tsk != current) || !ut_worker, "Invalid UMCG worker.")) + return; + + /* If the worker has no server, do nothing. */ + if (unlikely(!tsk->pinned_umcg_server_page)) + return; + + if (get_user_nofault(curr_state, &ut_worker->state_ts)) + goto die; + + /* + * The userspace is allowed to concurrently change a RUNNING worker's + * state only once in a "short" period of time, so we retry state + * change at most once. As this retry block is within a + * preempt_disable region, "short" is truly short here. + * + * See Documentation/userspace-api/umcg.txt for details. + */ +retry_once: + if (curr_state & UMCG_TF_LOCKED) + return; + + if (WARN_ONCE((curr_state & UMCG_TASK_STATE_MASK) != UMCG_TASK_RUNNING, + "Unexpected UMCG worker state.")) + goto die; + + next_state = curr_state & ~UMCG_TASK_STATE_MASK; + next_state |= UMCG_TASK_BLOCKED; + + ret = umcg_update_state(&ut_worker->state_ts, &curr_state, next_state, false); + if (ret == -EAGAIN) { + if (retried) + goto die; + + retried = true; + goto retry_once; + } + if (ret) + goto die; + + smp_mb(); /* Order state read/write above and getting next_tid below. */ + if (get_user_nofault(tid, &ut_worker->next_tid)) + goto die; + + *server_tid = tid; + return; + +die: + pr_warn("%s: killing task %d\n", __func__, current->pid); + force_sig(SIGKILL); +} + +/* Called from sched_submit_work(). Must not fault/sleep. */ +void umcg_wq_worker_sleeping(struct task_struct *tsk) +{ + u32 server_tid; + + /* + * Disable preemption so that retry_once in process_sleeping_worker + * works properly. + */ + preempt_disable(); + process_sleeping_worker(tsk, &server_tid); + preempt_enable(); + + if (server_tid) { + int ret = umcg_wake_idle_server_nofault(server_tid); + + if (ret && ret != -EAGAIN) + goto die; + } + + goto out; + +die: + pr_warn("%s: killing task %d\n", __func__, current->pid); + force_sig(SIGKILL); +out: + umcg_unpin_pages(); +} + +/** + * enqueue_idle_worker - push an idle worker onto idle_workers_ptr list/stack. + * + * Returns true on success, false on a fatal failure. + * + * See Documentation/userspace-api/umcg.txt for details. + */ +static bool enqueue_idle_worker(struct umcg_task __user *ut_worker) +{ + u64 __user *node = &ut_worker->idle_workers_ptr; + u64 __user *head_ptr; + u64 first = (u64)node; + u64 head; + + if (get_user(head, node) || !head) + return false; + + head_ptr = (u64 __user *)head; + + /* Mark the worker as pending. */ + if (put_user(UMCG_IDLE_NODE_PENDING, node)) + return false; + + /* Make the head point to the worker. */ + if (xchg_user_64(head_ptr, &first)) + return false; + + /* Make the worker point to the previous head. */ + if (put_user(first, node)) + return false; + + return true; +} + +/** + * get_idle_server - retrieve an idle server, if present. + * + * Returns true on success, false on a fatal failure. + */ +static bool get_idle_server(struct umcg_task __user *ut_worker, u32 *server_tid) +{ + u64 server_tid_ptr; + u32 tid; + + /* Empty result is OK. */ + *server_tid = 0; + + if (get_user(server_tid_ptr, &ut_worker->idle_server_tid_ptr)) + return false; + + if (!server_tid_ptr) + return false; + + tid = 0; + if (xchg_user_32((u32 __user *)server_tid_ptr, &tid)) + return false; + + *server_tid = tid; + return true; +} + +/* + * Returns true to wait for the userspace to schedule this worker, false + * to return to the userspace. + * + * In the common case, a BLOCKED worker is marked IDLE and enqueued + * to idle_workers_ptr list. The idle server is woken (if present). + * + * If a RUNNING worker is preempted, this function will trigger, in which + * case the worker is moved to IDLE state and its server is woken. + * + * Sets @server_tid to point to the server to be woken if the worker + * is going to sleep; sets @server_tid to point to the server assigned + * to this RUNNING worker if the worker is to return to the userspace. + */ +static bool process_waking_worker(struct task_struct *tsk, u32 *server_tid) +{ + struct umcg_task __user *ut_worker = tsk->umcg_task; + u64 curr_state, next_state; + + *server_tid = 0; + + if (WARN_ONCE((tsk != current) || !ut_worker, "Invalid umcg worker")) + return false; + + if (fatal_signal_pending(tsk)) + return false; + + if (get_user(curr_state, &ut_worker->state_ts)) + goto die; + + if ((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_RUNNING) { + u32 tid; + + /* Wakeup: wait but don't enqueue. */ + if (curr_state & UMCG_TF_LOCKED) + return true; + + smp_mb(); /* Order getting state and getting server_tid */ + if (get_user(tid, &ut_worker->next_tid)) + goto die; + + if (!tid) + /* RUNNING workers must have servers. */ + goto die; + + *server_tid = tid; + + /* pass-through: RUNNING with a server. */ + if (!(curr_state & UMCG_TF_PREEMPTED)) + return false; + + /* + * Fallthrough to mark the worker IDLE: the worker is + * PREEMPTED. + */ + } else if (unlikely((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_IDLE && + (curr_state & UMCG_TF_LOCKED))) + /* The worker prepares to sleep or to unregister. */ + return false; + + if (unlikely((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_IDLE)) + goto die; + + next_state = curr_state & ~UMCG_TASK_STATE_MASK; + next_state |= UMCG_TASK_IDLE; + + if (umcg_update_state(&ut_worker->state_ts, &curr_state, + next_state, true)) + goto die; + + if (!enqueue_idle_worker(ut_worker)) + goto die; + + smp_mb(); /* Order enqueuing the worker with getting the server. */ + if (!(*server_tid) && !get_idle_server(ut_worker, server_tid)) + goto die; + + return true; + +die: + pr_warn("umcg_process_waking_worker: killing task %d\n", current->pid); + force_sig(SIGKILL); + return false; +} + +/* + * Called from sched_update_worker(): defer all work until later, as + * sched_update_worker() may be called with in-kernel locks held. + */ +void umcg_wq_worker_running(struct task_struct *tsk) +{ + set_tsk_thread_flag(tsk, TIF_NOTIFY_RESUME); +} + +/* Called via TIF_NOTIFY_RESUME flag from exit_to_user_mode_loop. */ +void umcg_handle_resuming_worker(void) +{ + u32 server_tid; + + /* Avoid recursion by removing PF_UMCG_WORKER */ + current->flags &= ~PF_UMCG_WORKER; + + do { + bool should_wait; + + should_wait = process_waking_worker(current, &server_tid); + if (!should_wait) + break; + + if (server_tid) { + int ret = umcg_wake_idle_server(server_tid, true); + + if (ret && ret != -EAGAIN) + goto die; + } + + umcg_idle_loop(0); + } while (true); + + if (!server_tid) + /* No server => no reason to pin pages. */ + umcg_unpin_pages(); + else if (umcg_pin_pages(server_tid)) + goto die; + + goto out; + +die: + pr_warn("%s: killing task %d\n", __func__, current->pid); + force_sig(SIGKILL); +out: + current->flags |= PF_UMCG_WORKER; +} diff --git a/kernel/sys_ni.c b/kernel/sys_ni.c index d1944258cfc0..82d233aa2648 100644 --- a/kernel/sys_ni.c +++ b/kernel/sys_ni.c @@ -273,6 +273,10 @@ COND_SYSCALL(landlock_create_ruleset); COND_SYSCALL(landlock_add_rule); COND_SYSCALL(landlock_restrict_self); +/* kernel/sched/umcg.c */ +COND_SYSCALL(umcg_ctl); +COND_SYSCALL(umcg_wait); + /* arch/example/kernel/sys_example.c */ /* mm/fadvise.c */ From patchwork Sun Nov 21 21:20:38 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 12631067 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id A4B16C433F5 for ; Sun, 21 Nov 2021 21:23:12 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 04BB06B0075; Sun, 21 Nov 2021 16:21:01 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F15806B0078; Sun, 21 Nov 2021 16:21:00 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CA5286B007B; Sun, 21 Nov 2021 16:21:00 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0203.hostedemail.com [216.40.44.203]) by kanga.kvack.org (Postfix) with ESMTP id B5A966B0075 for ; Sun, 21 Nov 2021 16:21:00 -0500 (EST) Received: from smtpin07.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 6E01D84767 for ; Sun, 21 Nov 2021 21:20:50 +0000 (UTC) X-FDA: 78834207018.07.A85D879 Received: from mail-pg1-f171.google.com (mail-pg1-f171.google.com [209.85.215.171]) by imf14.hostedemail.com (Postfix) with ESMTP id 27D7F60019B0 for ; Sun, 21 Nov 2021 21:20:49 +0000 (UTC) Received: by mail-pg1-f171.google.com with SMTP id q12so13529997pgh.5 for ; Sun, 21 Nov 2021 13:20:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=posk.io; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=KmFQXKZcthHpKrqihBqeBtVNKdo1paLla9rrtvaUCuk=; b=dkS2cMxrcTah4X1p659pftCKDgfHz4gPEL0y51GX10V2ABEfJUHvH68JPmbM8kLRvs u75Iia9XcGG+/XdNpvYIJFum8QrIiYH68ZCLg1ocVPjlYdlI0ek+VHT9QX5h6yI68qgS KJvHiUGtV8fz8XLG/oq27r5E3pNUoSi+GL/4+3zDTg0NzZxINbNr9rP+YO15FXIuUKBY WYDSiEvQtEIGGslTHxZkPV1DXiTvndvrTZsOo7TyGznGNDBdlgkNnAOqoukeAa+tuVun 7Svajm4ejGh3Sgo9qCtbF4WlcRSMuK7jA+DMGCpFLt35bElaJZeHzxap0Uzy3//Yx+oW M9aw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=KmFQXKZcthHpKrqihBqeBtVNKdo1paLla9rrtvaUCuk=; b=ePdcYldJ/JF7XKx9WIThlcd9MREKz+gQ1qsog6V/5iaGWM99Ytp0PczkIrZUMTVYnx WQEXGofLsfp6O1DM0HlTtizR49mIP39UZzzvgSA+XRYSZomwkroAruXEAGp42ywxGolw ZzmuefFFX+AtuVmjxUiHjjpgRYZIB0RouYA7bYp2z6Id571WOMzmSpTI7JhPWftlsJld XKeJ12HrxLuTdDOAZsqUUEW6wOMVCDQ92vzosuemEkwXgu4RajG4TaUYTDBnyHSEGd8U D8z6pHwzbqWN16BHCDC5RslXQCy3DSfcgfhkwO2ujYFJFr0D5SiKyPjSXKUYfY/mxRmd TaWg== X-Gm-Message-State: AOAM533rgm8J5fCzCtPP4N3vUqe/HpXHDFwXY/+bhN4RZuNif/UTRAJV 0dsJrUasPzGwKUop2z+HWoyy/IeSpmdWrQ== X-Google-Smtp-Source: ABdhPJwGaqryvchinGlWpADl4Ep6WWoApRfKqlt720KzvituOPJlwdQKHiRoTCAaj1mEf3PZgsm1wA== X-Received: by 2002:aa7:9990:0:b0:4a1:57ff:3369 with SMTP id k16-20020aa79990000000b004a157ff3369mr39609506pfh.31.1637529648693; Sun, 21 Nov 2021 13:20:48 -0800 (PST) Received: from posk-p1g4.localdomain (23-118-52-46.lightspeed.sntcca.sbcglobal.net. [23.118.52.46]) by smtp.gmail.com with ESMTPSA id k8sm6207924pfu.75.2021.11.21.13.20.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 21 Nov 2021 13:20:48 -0800 (PST) From: Peter Oskolkov X-Google-Original-From: Peter Oskolkov To: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org Cc: Paul Turner , Ben Segall , Peter Oskolkov , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: [PATCH v0.9 4/6] sched/umcg, lib/umcg: implement libumcg Date: Sun, 21 Nov 2021 13:20:38 -0800 Message-Id: <20211121212040.8649-5-posk@google.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211121212040.8649-1-posk@google.com> References: <20211121212040.8649-1-posk@google.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 27D7F60019B0 X-Stat-Signature: qo4zrtx9rwxw4zyx9ffbpewd4yfkbw1s Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=posk.io header.s=google header.b=dkS2cMxr; dmarc=none; spf=pass (imf14.hostedemail.com: domain of posk@posk.io designates 209.85.215.171 as permitted sender) smtp.mailfrom=posk@posk.io X-Rspamd-Server: rspam02 X-HE-Tag: 1637529649-789607 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Implement libumcg in tools/lib/umcg. Define higher-level UMCG API that hides kernel-level UMCG API intricacies. As a higher-level API, libumcg makes subtle changes to server/worker interactions, compared to the kernel UMCG API, and introduces the following new concepts: - UMCG Group: a collection of servers and workers in a process that can interact with each other; UMCG groups are useful to partition servers and workers within a process in order to, for example, affine work to specific NUMA nodes; - UMCG basic tasks: these are UMCG servers, from the kernel point of view; they do not interact with UMCG workers and thus do not need in UMCG groups; used for cooperative wait/wake/swap operations. The main difference of server/worker interaction in libumcg vs the kernel-side UMCG API is that a wakeup can be queued: if umcg_wake() is called on a RUNNING UMCG task, the fact is recorded (in the userspace), and when the task calls umcg_wait() or umcg_swap(), the wakeup is consumed and the task is not marked IDLE. Libumcg exports the following API: umcg_enabled() umcg_get_utid() umcg_set_task_tag() umcg_get_task_tag() umcg_create_group() umcg_destroy_group() umcg_register_basic_task() umcg_register_worker() umcg_register_server() umcg_unregister_task() umcg_wait() umcg_wake() umcg_swap() umcg_get_idle_worker() umcg_run_worker() umcg_preempt_worker() umcg_get_time_ns() See tools/lib/umcg/libumcg.txt for details. Notes: - this is still somewhat work-in-progress: while the kernel side code has been more or less stable over the last couple of months, the userspace side of things is less so; - while libumcg is intended to be the main/primary/only direct user of the kernel UMCG API, at the moment the implementation is more geared more towards testing and correctness than live production usage, with a lot of asserts and similar development helpers; - I have a number of umcg selftests that I plan to clean up and post shortly. Signed-off-by: Peter Oskolkov --- tools/lib/umcg/.gitignore | 4 + tools/lib/umcg/Makefile | 11 + tools/lib/umcg/libumcg.c | 1201 +++++++++++++++++++++++++++++++++++++ tools/lib/umcg/libumcg.h | 299 +++++++++ 4 files changed, 1515 insertions(+) create mode 100644 tools/lib/umcg/.gitignore create mode 100644 tools/lib/umcg/Makefile create mode 100644 tools/lib/umcg/libumcg.c create mode 100644 tools/lib/umcg/libumcg.h -- 2.25.1 diff --git a/tools/lib/umcg/.gitignore b/tools/lib/umcg/.gitignore new file mode 100644 index 000000000000..ea55ae666041 --- /dev/null +++ b/tools/lib/umcg/.gitignore @@ -0,0 +1,4 @@ +PDX-License-Identifier: GPL-2.0-only +libumcg.a +libumcg.o + diff --git a/tools/lib/umcg/Makefile b/tools/lib/umcg/Makefile new file mode 100644 index 000000000000..ea4439d44917 --- /dev/null +++ b/tools/lib/umcg/Makefile @@ -0,0 +1,11 @@ +# SPDX-License-Identifier: GPL-2.0 + +CFLAGS += -g -I../../include/ -I../../../usr/include/ + +libumcg.a: libumcg.o + ar rc libumcg.a libumcg.o + +libumcg.o: libumcg.c + +clean : + rm libumcg.a libumcg.o diff --git a/tools/lib/umcg/libumcg.c b/tools/lib/umcg/libumcg.c new file mode 100644 index 000000000000..b5317024fc0d --- /dev/null +++ b/tools/lib/umcg/libumcg.c @@ -0,0 +1,1201 @@ +// SPDX-License-Identifier: GPL-2.0 +#define _GNU_SOURCE +#include "libumcg.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +static int sys_umcg_ctl(uint32_t flags, struct umcg_task *umcg_task) +{ + return syscall(__NR_umcg_ctl, flags, umcg_task); +} + +static int sys_umcg_wait(uint32_t flags, uint64_t abs_timeout) +{ + return syscall(__NR_umcg_wait, flags, abs_timeout); +} + +bool umcg_enabled(void) +{ + int ret = sys_umcg_ctl(UMCG_CTL_REGISTER, NULL); + + if (ret && errno == EINVAL) + return true; + + return false; +} + +uint64_t umcg_get_time_ns(void) +{ + struct timespec ts; + + if (clock_gettime(CLOCK_REALTIME, &ts)) { + fprintf(stderr, "clock_gettime failed\n"); + abort(); + } + + return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec; +} + +struct umcg_task_tls; + +/** + * struct umcg_group - describes UMCG group. + * + * See tools/lib/umcg/libumcg.txt for detals. + */ +struct umcg_group { + /** + * @idle_workers_head: points to the kernel-side list of idle + * workers, i.e. the address of this field + * is passed to the kernel in + * struct umcg_task.idle_workers_ptr. + */ + uint64_t idle_workers_head; + + /** + * @nr_tasks: the number of tasks (servers and workers) registered + * in this group. + */ + uint64_t nr_tasks; + + /** + * @idle_worker_lock: protects @idle_workers below. + */ + pthread_spinlock_t idle_worker_lock; + + /** + * @idle_server_lock: protects @idle_servers below. + */ + pthread_spinlock_t idle_server_lock; + + /** + * @idle_workers: points to the userspace-side list of idle workers. + * + * When a server polls for an idle worker via umcg_poll_worker(), + * the server first consults @idle_workers; if the list is empty, + * the value of the variable is swapped with @idle_workers_head. + */ + uint64_t *idle_workers; + + /** + * @idle_servers: points to the userspace-side list of idle servers. + * + * When a server polls for an idle worker via umcg_poll_worker(), + * and none is available, the server is added to the list and blocks + * via sys_umcg_wait(). + */ + struct umcg_task_tls *idle_servers; + + /** + * @idle_server_tid: the TID of one of the idle servers. + * + * The address of this field is passed to the kernel in + * struct umct_task.idle_server_tid_ptr. + */ + uint32_t idle_server_tid; +} __attribute((aligned(8))); + +/** + * struct umcg_task_tls - per thread struct used to identify/manage UMCG tasks + * + * Each UMCG task requires an instance of struct umcg_task passed to + * sys_umcg_ctl. This struct contains it, as well as several additional + * fields useful for the userspace UMCG API. + * + * The alignment is driven by the alignment of struct umcg_task. + */ +struct umcg_task_tls { + struct umcg_task umcg_task; + struct umcg_group *group; /* read only */ + umcg_tid peer; /* server or worker or UMCG_NONE */ + umcg_tid self; /* read only */ + intptr_t tag; + pid_t tid; /* read only */ + bool worker; /* read only */ + + struct umcg_task_tls *next; /* used in group->idle_servers */ +} __attribute((aligned(8 * sizeof(uint64_t)))); + +static thread_local struct umcg_task_tls *umcg_task_tls; + +umcg_tid umcg_get_utid(void) +{ + return (umcg_tid)&umcg_task_tls; +} + +static struct umcg_task_tls *utid_to_utls(umcg_tid utid) +{ + assert(utid != UMCG_NONE); + return *(struct umcg_task_tls **)utid; +} + +uint64_t umcg_get_task_state(umcg_tid task) +{ + struct umcg_task_tls *utls = utid_to_utls(task); + uint64_t state; + + if (!utls) + return UMCG_TASK_NONE; + + state = atomic_load_explicit(&utls->umcg_task.state_ts, memory_order_acquire); + return state & UMCG_TASK_STATE_MASK_FULL; +} + +/* Update the state variable, set new timestamp. */ +static bool umcg_update_state(uint64_t *state, uint64_t *prev, uint64_t next) +{ + uint64_t prev_ts = (*prev) >> (64 - UMCG_STATE_TIMESTAMP_BITS); + struct timespec now; + uint64_t next_ts; + int res; + + /* + * clock_gettime(CLOCK_MONOTONIC, ...) takes less than 20ns on a + * typical Intel processor on average, even when run concurrently, + * so the overhead is low enough for most applications. + * + * If this is still too high, `next_ts = prev_ts + 1` should work + * as well. The only real requirement is that the "timestamps" are + * uniqueue per thread within a reasonable time frame. + */ + res = clock_gettime(CLOCK_MONOTONIC, &now); + assert(!res); + next_ts = (now.tv_sec * NSEC_PER_SEC + now.tv_nsec) >> + UMCG_STATE_TIMESTAMP_GRANULARITY; + + /* Cut higher order bits. */ + next_ts &= ((1ULL << UMCG_STATE_TIMESTAMP_BITS) - 1); + + if (next_ts == prev_ts) + ++next_ts; + +#ifndef NDEBUG + if (prev_ts > next_ts) { + fprintf(stderr, "%s: time goes back: prev_ts: %lu " + "next_ts: %lu diff: %lu\n", __func__, + prev_ts, next_ts, prev_ts - next_ts); + } +#endif + + /* Remove old timestamp, if any. */ + next &= ((1ULL << (64 - UMCG_STATE_TIMESTAMP_BITS)) - 1); + + /* Set the new timestamp. */ + next |= (next_ts << (64 - UMCG_STATE_TIMESTAMP_BITS)); + + /* + * TODO: review whether memory order below can be weakened to + * memory_order_acq_rel for success and memory_order_acquire for + * failure. + */ + return atomic_compare_exchange_strong_explicit(state, prev, next, + memory_order_seq_cst, memory_order_seq_cst); +} + +static bool umcg_worker_in_idle_queue(umcg_tid worker) +{ + struct umcg_task_tls *worker_utls = utid_to_utls(worker); + struct umcg_task *worker_ut = &worker_utls->umcg_task; + + assert(worker_utls->worker); + + return (uint64_t)&worker_utls->group->idle_workers_head != + atomic_load_explicit(&worker_ut->idle_workers_ptr, + memory_order_acquire); +} + +void umcg_set_task_tag(umcg_tid utid, intptr_t tag) +{ + utid_to_utls(utid)->tag = tag; +} + +intptr_t umcg_get_task_tag(umcg_tid utid) +{ + return utid_to_utls(utid)->tag; +} + +static bool try_task_lock(struct umcg_task_tls *task, uint64_t expected_state, + uint64_t new_state) +{ + uint64_t next; + uint64_t prev = atomic_load_explicit(&task->umcg_task.state_ts, + memory_order_acquire); + + if (prev & UMCG_TF_LOCKED) + return false; + + if ((prev & UMCG_TASK_STATE_MASK) != expected_state) + return false; + + next = (prev & ~UMCG_TASK_STATE_MASK) | new_state | UMCG_TF_LOCKED; + return umcg_update_state(&task->umcg_task.state_ts, &prev, next); +} + +static void task_lock(struct umcg_task_tls *task, uint64_t expected_state, + uint64_t new_state) +{ + int loop_counter = 0; + + while (!try_task_lock(task, expected_state, new_state)) + assert(++loop_counter < 1000 * 1000 * 100); +} + +static void task_unlock(struct umcg_task_tls *task, uint64_t expected_state, + uint64_t new_state) +{ + bool ok; + uint64_t next; + uint64_t prev = atomic_load_explicit(&task->umcg_task.state_ts, + memory_order_acquire); + + next = ((prev & ~UMCG_TASK_STATE_MASK_FULL) | new_state) & ~UMCG_TF_LOCKED; + assert(next != prev); + assert((prev & UMCG_TASK_STATE_MASK_FULL & ~UMCG_TF_LOCKED) == expected_state); + + ok = umcg_update_state(&task->umcg_task.state_ts, &prev, next); + assert(ok); +} + +umcg_tid umcg_register_basic_task(intptr_t tag) +{ + int ret; + + if (umcg_task_tls != NULL) { + errno = EINVAL; + return UMCG_NONE; + } + + umcg_task_tls = malloc(sizeof(struct umcg_task_tls)); + if (!umcg_task_tls) { + errno = ENOMEM; + return UMCG_NONE; + } + memset(umcg_task_tls, 0, sizeof(struct umcg_task_tls)); + + umcg_task_tls->umcg_task.state_ts = UMCG_TASK_RUNNING; + umcg_task_tls->self = (umcg_tid)&umcg_task_tls; + umcg_task_tls->tag = tag; + umcg_task_tls->tid = gettid(); + + ret = sys_umcg_ctl(UMCG_CTL_REGISTER, &umcg_task_tls->umcg_task); + if (ret) { + free(umcg_task_tls); + umcg_task_tls = NULL; + errno = ret; + return UMCG_NONE; + } + + return umcg_task_tls->self; +} + +static umcg_tid umcg_register_task_in_group(umcg_t group_id, intptr_t tag, + bool server) +{ + int ret; + uint32_t self_tid; + struct umcg_group *group; + struct umcg_task_tls *curr; + + if (group_id == UMCG_NONE) { + errno = EINVAL; + return UMCG_NONE; + } + + if (umcg_task_tls != NULL) { + errno = EINVAL; + return UMCG_NONE; + } + + group = (struct umcg_group *)group_id; + + curr = malloc(sizeof(struct umcg_task_tls)); + if (!curr) { + errno = ENOMEM; + return UMCG_NONE; + } + memset(curr, 0, sizeof(struct umcg_task_tls)); + + self_tid = gettid(); + curr->umcg_task.state_ts = server ? UMCG_TASK_RUNNING : UMCG_TASK_BLOCKED; + curr->umcg_task.idle_server_tid_ptr = server ? 0UL : + (uint64_t)&group->idle_server_tid; + curr->umcg_task.idle_workers_ptr = + (uint64_t)&group->idle_workers_head; + curr->group = group; + curr->tag = tag; + curr->tid = self_tid; + curr->self = (umcg_tid)&umcg_task_tls; + curr->worker = !server; + + /* + * Need to set umcg_task_tls before registering, as a server + * may pick up this worker immediately, and use @self. + */ + atomic_store_explicit(&umcg_task_tls, curr, memory_order_release); + + ret = sys_umcg_ctl(server ? UMCG_CTL_REGISTER : + UMCG_CTL_REGISTER | UMCG_CTL_WORKER, + &curr->umcg_task); + if (ret) { + free(curr); + errno = ret; + atomic_store_explicit(&umcg_task_tls, NULL, memory_order_release); + return UMCG_NONE; + } + + atomic_fetch_add_explicit(&group->nr_tasks, 1, memory_order_relaxed); + + return umcg_task_tls->self; +} + +umcg_tid umcg_register_worker(umcg_t group_id, intptr_t tag) +{ + return umcg_register_task_in_group(group_id, tag, false); +} + +umcg_tid umcg_register_server(umcg_t group_id, intptr_t tag) +{ + return umcg_register_task_in_group(group_id, tag, true); +} + +int umcg_unregister_task(void) +{ + int ret; + + if (!umcg_task_tls) { + errno = EINVAL; + return -1; + } + + /* If this is a worker, wake the server. */ + if (umcg_task_tls->worker) { + struct umcg_task_tls *curr = umcg_task_tls; + struct umcg_task_tls *utls_server; + + task_lock(curr, UMCG_TASK_RUNNING, UMCG_TASK_IDLE); + utls_server = utid_to_utls(curr->peer); + assert(utls_server->tid == atomic_load_explicit( + &curr->umcg_task.next_tid, + memory_order_acquire)); + curr->peer = UMCG_NONE; + atomic_store_explicit(&curr->umcg_task.next_tid, 0, + memory_order_release); + + utls_server->peer = UMCG_NONE; + atomic_store_explicit(&utls_server->umcg_task.next_tid, 0, + memory_order_release); + + /* Keep the worker locked to avoid needing the server. */ + if (utls_server) { + curr->worker = false; /* umcg_wake tries to lock */ + ret = umcg_wake(utls_server->self, false); + assert(!ret || errno == ESRCH); + } + } + + ret = sys_umcg_ctl(UMCG_CTL_UNREGISTER, NULL); + if (ret) { + errno = ret; + return -1; + } + + if (umcg_task_tls->group) + atomic_fetch_sub_explicit(&umcg_task_tls->group->nr_tasks, 1, + memory_order_relaxed); + + free(umcg_task_tls); + atomic_store_explicit(&umcg_task_tls, NULL, memory_order_release); + return 0; +} + +/* Helper return codes. */ +enum umcg_prepare_op_result { + UMCG_OP_DONE, + UMCG_OP_SYS, + UMCG_OP_AGAIN, + UMCG_OP_ERROR +}; + +static enum umcg_prepare_op_result umcg_prepare_wait_may_lock(void) +{ + struct umcg_task *ut; + uint64_t prev_state, next_state; + + if (!umcg_task_tls) { + errno = EINVAL; + return UMCG_OP_ERROR; + } + + ut = &umcg_task_tls->umcg_task; + + prev_state = atomic_load_explicit(&ut->state_ts, memory_order_acquire); + next_state = umcg_task_tls->worker ? + UMCG_TASK_IDLE | UMCG_TF_LOCKED | UMCG_UTF_WORKER_IN_WAIT : + UMCG_TASK_IDLE; + if (((prev_state & UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_RUNNING) && + umcg_update_state(&ut->state_ts, &prev_state, next_state)) + return UMCG_OP_SYS; + + if ((prev_state & UMCG_TASK_STATE_MASK_FULL) != + (UMCG_TASK_RUNNING | UMCG_UTF_WAKEUP_QUEUED)) { +#ifndef NDEBUG + fprintf(stderr, "libumcg: unexpected state before wait: %lu\n", + prev_state); + assert(false); +#endif + errno = EINVAL; + return UMCG_OP_ERROR; + } + + if (umcg_update_state(&ut->state_ts, &prev_state, UMCG_TASK_RUNNING)) + return UMCG_OP_DONE; + +#ifndef NDEBUG + /* Raced with another wait/wake? This is not supported. */ + fprintf(stderr, "libumcg: failed to remove the wakeup flag: %lu\n", + prev_state); + assert(false); +#endif + errno = EINVAL; + return UMCG_OP_ERROR; +} + +/* Always return -1 because the user needs to see ETIMEDOUT in errno */ +static int handle_timedout(void) +{ + struct umcg_task *ut = &umcg_task_tls->umcg_task; + uint64_t umcg_state; + +retry: + /* Restore RUNNING state if the task is still IDLE. */ + umcg_state = atomic_load_explicit(&ut->state_ts, + memory_order_acquire); + if ((umcg_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_RUNNING) + return -1; + + assert((umcg_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_IDLE); + + if (umcg_update_state(&ut->state_ts, &umcg_state, UMCG_TASK_RUNNING)) + return -1; + + /* A wakeup could have been queued. */ + goto retry; +} + +static int umcg_do_wait(uint64_t timeout) +{ + struct umcg_task *ut = &umcg_task_tls->umcg_task; + uint32_t flags = 0; + + /* If this is a worker, need to change the state of the server. */ + if (umcg_task_tls->worker && + atomic_load_explicit(&ut->next_tid, memory_order_acquire)) { + bool ok; + struct umcg_task *server_ut = + &utid_to_utls(umcg_task_tls->peer)->umcg_task; + uint64_t server_state = atomic_load_explicit(&server_ut->state_ts, + memory_order_acquire); + + assert((server_state & UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_IDLE); + ok = umcg_update_state(&server_ut->state_ts, + &server_state, UMCG_TASK_RUNNING); + assert(ok); + } else if (!umcg_task_tls->worker) + atomic_store_explicit(&ut->next_tid, 0, memory_order_release); + + do { + uint64_t umcg_state; + int ret; + + ret = sys_umcg_wait(flags, timeout); + if (!ret) + return 0; + + if (ret && errno == EINTR) { + umcg_state = atomic_load_explicit(&ut->state_ts, + memory_order_acquire) & UMCG_TASK_STATE_MASK; + if (umcg_state == UMCG_TASK_RUNNING) + return 0; + continue; + } + + if (errno == ETIMEDOUT) + return handle_timedout(); + + return -1; + } while (true); +} + +int umcg_wait(uint64_t timeout) +{ + switch (umcg_prepare_wait_may_lock()) { + case UMCG_OP_DONE: + return 0; + case UMCG_OP_SYS: + break; + case UMCG_OP_ERROR: + return -1; + default: + assert(false); + return -1; + } + + return umcg_do_wait(timeout); +} + +static void enqueue_idle_worker(struct umcg_task_tls *utls) +{ + struct umcg_task *ut = &utls->umcg_task; + uint64_t *node = &ut->idle_workers_ptr; + uint64_t head = *node; + uint64_t *head_ptr = (uint64_t *)head; + uint64_t first = (uint64_t)node; + + assert(utls->worker); + assert(&utls->group->idle_workers_head == head_ptr); + + /* Mark the worker as pending. */ + atomic_store_explicit(node, UMCG_IDLE_NODE_PENDING, memory_order_release); + + /* Make the head point to the worker. */ + first = atomic_exchange_explicit(head_ptr, first, memory_order_acq_rel); + + /* Make the worker point to the previous head. */ + atomic_store_explicit(node, first, memory_order_release); +} + +static enum umcg_prepare_op_result umcg_prepare_wake_may_lock( + struct umcg_task_tls *next_utls, bool for_swap) +{ + struct umcg_task *next_ut = &next_utls->umcg_task; + uint64_t curr_state, next_state; + enum umcg_prepare_op_result result = UMCG_OP_DONE; + bool enqueue_worker = false; + + curr_state = atomic_load_explicit(&next_ut->state_ts, memory_order_acquire); + + if (curr_state & (UMCG_TF_LOCKED | UMCG_UTF_WAKEUP_QUEUED)) + return UMCG_OP_AGAIN; + + /* Start with RUNNING tasks. */ + if ((curr_state & UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_RUNNING) + next_state = UMCG_TASK_RUNNING | UMCG_UTF_WAKEUP_QUEUED; + else if (curr_state & UMCG_UTF_WORKER_IN_WAIT) { + /* Next, check workers in wait. */ + assert(next_utls->worker); + assert((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_IDLE); + + if (for_swap) { + next_state = UMCG_TASK_RUNNING; + result = UMCG_OP_SYS; + } else { + next_state = UMCG_TASK_IDLE; + enqueue_worker = true; + } + } else if ((curr_state & UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_IDLE) { + /* Next, check IDLE tasks. */ + if (next_utls->worker) { + if (for_swap) { + next_state = UMCG_TASK_RUNNING | UMCG_TF_LOCKED; + result = UMCG_OP_SYS; + } else { + return UMCG_OP_AGAIN; + } + } else { + atomic_store_explicit(&next_utls->umcg_task.next_tid, + 0, memory_order_release); + next_state = UMCG_TASK_RUNNING; + result = UMCG_OP_SYS; + } + } else { + /* Finally, deal with BLOCKED workers. */ + assert((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_BLOCKED); + assert(next_utls->worker); + + return UMCG_OP_AGAIN; + } + + if (umcg_update_state(&next_ut->state_ts, &curr_state, next_state)) { + if (enqueue_worker) + enqueue_idle_worker(next_utls); + return result; + } + + return UMCG_OP_AGAIN; +} + +static int umcg_do_wake_or_swap(uint32_t next_tid, bool should_wait, + uint64_t timeout, bool wf_current_cpu, + struct umcg_task_tls *next_utls) +{ + struct umcg_task *ut; + uint32_t flags = 0; + uint32_t server_tid = 0; + int ret; + + /* wf_current_cpu is possible in wake-only scenarios. */ + assert(!should_wait || !wf_current_cpu); + assert(umcg_task_tls != NULL); + + ut = &umcg_task_tls->umcg_task; + + /* + * This is a worker waking another task: lock it so that next_tid + * is not interpreted as a server if this worker pagefaults. + */ + if (umcg_task_tls->worker && !should_wait) { + server_tid = atomic_load_explicit(&ut->next_tid, + memory_order_acquire); + assert(server_tid); + assert(utid_to_utls(umcg_task_tls->peer)->tid == server_tid); + task_lock(umcg_task_tls, UMCG_TASK_RUNNING, UMCG_TASK_IDLE); + } + + atomic_store_explicit(&ut->next_tid, next_tid, memory_order_release); + + if (!should_wait) + flags |= UMCG_WAIT_WAKE_ONLY; + if (wf_current_cpu) + flags |= UMCG_WAIT_WF_CURRENT_CPU; + + if (next_utls && next_utls->worker) + task_unlock(next_utls, UMCG_TASK_RUNNING, UMCG_TASK_RUNNING); + ret = sys_umcg_wait(flags, should_wait ? timeout : 0); + + /* If we locked this worker, unlock it. */ + if (server_tid) { + atomic_store_explicit(&ut->next_tid, server_tid, + memory_order_release); + task_unlock(umcg_task_tls, UMCG_TASK_IDLE, UMCG_TASK_RUNNING); + } + + if (ret && errno == ETIMEDOUT) + return handle_timedout(); + + return ret; +} + +int umcg_wake(umcg_tid next, bool wf_current_cpu) +{ + struct umcg_task_tls *utls = utid_to_utls(next); + uint64_t loop_counter = 0; + + if (!utls) { + errno = EINVAL; + return -1; + } + +again: + assert(++loop_counter < (1ULL << 31)); + switch (umcg_prepare_wake_may_lock(utls, false /* for_swap */)) { + case UMCG_OP_DONE: + return 0; + case UMCG_OP_SYS: + break; + case UMCG_OP_ERROR: + return -1; + case UMCG_OP_AGAIN: + goto again; + default: + assert(false); + return -1; + } + + return umcg_do_wake_or_swap(utls->tid, false, 0, wf_current_cpu, utls); +} + +static void transfer_server_locked(struct umcg_task_tls *next) +{ + struct umcg_task_tls *curr = umcg_task_tls; + struct umcg_task_tls *server = utid_to_utls(curr->peer); + + atomic_thread_fence(memory_order_acquire); + assert(curr->worker); + assert(next->worker); + assert(curr->peer != UMCG_NONE); + assert(next->peer == UMCG_NONE); + + next->peer = curr->peer; + curr->peer = UMCG_NONE; + next->umcg_task.next_tid = curr->umcg_task.next_tid; + curr->umcg_task.next_tid = 0; + + server->peer = next->self; + server->umcg_task.next_tid = next->tid; + atomic_thread_fence(memory_order_release); +} + +int umcg_swap(umcg_tid next, uint64_t timeout) +{ + struct umcg_task_tls *utls = utid_to_utls(next); + bool should_wake, should_wait; + uint64_t loop_counter = 0; + + assert(umcg_task_tls); + +again: + assert(++loop_counter < (1ULL << 31)); + switch (umcg_prepare_wake_may_lock(utls, true /* for_swap */)) { + case UMCG_OP_DONE: + should_wake = false; + break; + case UMCG_OP_SYS: + should_wake = true; + break; + case UMCG_OP_ERROR: + return -1; + case UMCG_OP_AGAIN: + goto again; + default: + assert(false); + } + + switch (umcg_prepare_wait_may_lock()) { + case UMCG_OP_DONE: + should_wait = false; + break; + case UMCG_OP_SYS: + should_wait = true; + break; + case UMCG_OP_ERROR: + return -1; + default: + assert(false); + } + + if (should_wait && should_wake && umcg_task_tls->worker) + transfer_server_locked(utls); + + if (should_wake) + return umcg_do_wake_or_swap(utls->tid, should_wait, timeout, + false, utls); + + if (should_wait) + return umcg_do_wait(timeout); + + return 0; +} + +/* A noop SIGUSR1 handler, used in worker preemption. */ +static void sigusr_handler(int signum) +{ +} + +umcg_t umcg_create_group(uint32_t flags) +{ + struct umcg_group *group; + int res; + + if (flags && flags != UMCG_GROUP_ENABLE_PREEMPTION) { + errno = EINVAL; + return UMCG_NONE; + } + + group = malloc(sizeof(struct umcg_group)); + if (!group) { + errno = ENOMEM; + return UMCG_NONE; + } + + memset(group, 0, sizeof(*group)); + + res = pthread_spin_init(&group->idle_worker_lock, PTHREAD_PROCESS_PRIVATE); + if (res) { + errno = res; + goto error; + } + + res = pthread_spin_init(&group->idle_server_lock, PTHREAD_PROCESS_PRIVATE); + if (res) { + errno = res; + res = pthread_spin_destroy(&group->idle_worker_lock); + assert(!res); + goto error; + } + + if (flags & UMCG_GROUP_ENABLE_PREEMPTION) { + if (SIG_ERR == signal(SIGUSR1, sigusr_handler)) { + res = pthread_spin_destroy(&group->idle_worker_lock); + assert(!res); + res = pthread_spin_destroy(&group->idle_server_lock); + assert(!res); + goto error; + } + } + + return (intptr_t)group; + +error: + free(group); + return UMCG_NONE; +} + +int umcg_destroy_group(umcg_t umcg) +{ + int res; + struct umcg_group *group = (struct umcg_group *)umcg; + + if (atomic_load_explicit(&group->nr_tasks, memory_order_acquire)) { + errno = EBUSY; + return -1; + } + + res = pthread_spin_destroy(&group->idle_worker_lock); + assert(!res); + res = pthread_spin_destroy(&group->idle_server_lock); + assert(!res); + + free(group); + return 0; +} + +static void detach_worker(void) +{ + struct umcg_task_tls *server_utls = umcg_task_tls; + struct umcg_task_tls *worker_utls; + + assert(server_utls->group != NULL); + + atomic_thread_fence(memory_order_acquire); + if (!server_utls->peer) + return; + + worker_utls = utid_to_utls(server_utls->peer); + assert(server_utls->peer == worker_utls->self); + assert(worker_utls->peer == server_utls->self); + + umcg_task_tls->umcg_task.next_tid = 0; + worker_utls->umcg_task.next_tid = 0; + worker_utls->peer = UMCG_NONE; + server_utls->peer = UMCG_NONE; + + atomic_thread_fence(memory_order_release); +} + +umcg_tid umcg_run_worker(umcg_tid worker) +{ + struct umcg_task_tls *worker_utls = utid_to_utls(worker); + struct umcg_task_tls *server_utls = umcg_task_tls; + struct umcg_task *server_ut = &umcg_task_tls->umcg_task; + struct umcg_task *worker_ut; + uint64_t curr_state, next_state; + int ret; + bool ok; + + assert(server_utls->group != NULL); + assert(server_utls->group == worker_utls->group); + assert(worker_utls->worker); + + atomic_thread_fence(memory_order_acquire); + assert(server_utls->peer == UMCG_NONE); + assert(worker_utls->peer == UMCG_NONE); + + worker_ut = &worker_utls->umcg_task; + + assert(!umcg_worker_in_idle_queue(worker)); + + /* + * Mark the server IDLE before marking the worker RUNNING: preemption + * can happen immediately after the worker is marked RUNNING. + */ + curr_state = atomic_load_explicit(&server_ut->state_ts, + memory_order_acquire); + assert((curr_state & UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_RUNNING); + ok = umcg_update_state(&server_ut->state_ts, &curr_state, UMCG_TASK_IDLE); + assert(ok); + + /* Lock the worker in preparation to run it. */ + curr_state = atomic_load_explicit(&worker_ut->state_ts, + memory_order_acquire); + assert((curr_state & UMCG_TASK_STATE_MASK) == UMCG_TASK_IDLE); + assert(!(curr_state & UMCG_TF_LOCKED)); + next_state = curr_state & UMCG_UTF_WAKEUP_QUEUED ? + UMCG_TASK_RUNNING | UMCG_UTF_WAKEUP_QUEUED : + UMCG_TASK_RUNNING; + ok = umcg_update_state(&worker_ut->state_ts, &curr_state, + next_state | UMCG_TF_LOCKED); + + assert(ok); + + /* Attach the server to the worker. */ + atomic_thread_fence(memory_order_acquire); + server_ut->next_tid = worker_utls->tid; + worker_ut->next_tid = server_utls->tid; + worker_utls->peer = server_utls->self; + server_utls->peer = worker; + + atomic_thread_fence(memory_order_release); + task_unlock(worker_utls, next_state, next_state); + + ret = sys_umcg_wait(0, 0); + + atomic_thread_fence(memory_order_acquire); + if (!server_utls->peer) { + assert(server_ut->next_tid == 0); + /* + * The worker woke early due to umcg_state change + * and unregistered/exited. + */ + assert(!ret || errno == ESRCH); + errno = 0; + return UMCG_NONE; + } + + assert(!ret); + + /* Detach the server from the worker. */ + worker_utls = utid_to_utls(server_utls->peer); + detach_worker(); + + return worker_utls->self; +} + +int umcg_preempt_worker(umcg_tid worker) +{ + struct umcg_task_tls *worker_utls = utid_to_utls(worker); + struct umcg_task *worker_ut = &worker_utls->umcg_task; + uint32_t worker_tid = worker_utls->tid; + uint64_t curr_state; + int ret; + + curr_state = atomic_load_explicit(&worker_ut->state_ts, + memory_order_acquire); + if ((curr_state & UMCG_TASK_STATE_MASK_FULL) != UMCG_TASK_RUNNING) { + errno = EAGAIN; + return -1; + } + + if (!umcg_update_state(&worker_ut->state_ts, &curr_state, + UMCG_TASK_RUNNING | UMCG_TF_PREEMPTED)) { + errno = EAGAIN; + return -1; + } + + /* + * It is possible that this thread is descheduled here, the worker + * pagefaults, wakes up, and then exits; in this case tgkill() below + * will fail with errno == ESRCH. + */ + ret = tgkill(getpid(), worker_tid, SIGUSR1); + assert(!ret || errno == ESRCH); + return 0; +} + +static void wake_idle_server(void) +{ + struct umcg_group *group = umcg_task_tls->group; + int res; + + res = pthread_spin_lock(&group->idle_server_lock); + assert(!res); + + if (group->idle_servers) { + struct umcg_task_tls *server = group->idle_servers; + + group->idle_servers = server->next; + server->next = NULL; + + assert((atomic_load_explicit(&server->umcg_task.state_ts, + memory_order_acquire) & + UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_IDLE); + + res = umcg_wake(server->self, false); + assert(!res); + } + + res = pthread_spin_unlock(&group->idle_server_lock); + assert(!res); +} + +static umcg_tid get_idle_worker(void) +{ + struct umcg_group *group = umcg_task_tls->group; + umcg_tid result = UMCG_NONE; + uint64_t *head; + int res; + + res = pthread_spin_lock(&group->idle_worker_lock); + assert(!res); + + head = group->idle_workers; + +once_again: + /* First, check the userspace idle worker list. */ + if (head) { + uint64_t next; + struct umcg_task *worker; + struct umcg_task_tls *worker_utls; + + worker = container_of(head, struct umcg_task, idle_workers_ptr); + worker_utls = container_of(worker, struct umcg_task_tls, umcg_task); + + /* Spin while the worker is pending. */ + do { + next = atomic_load_explicit(head, memory_order_acquire); + } while (next == UMCG_IDLE_NODE_PENDING); + + /* Wait for the worker's server to detach in umcg_run_worker(). */ + while (atomic_load_explicit(&worker_utls->peer, + memory_order_relaxed)) + ; + + /* Pull the worker out of the idle worker list. */ + group->idle_workers = (uint64_t *)next; + atomic_store_explicit(&worker->idle_workers_ptr, + (uint64_t)&group->idle_workers_head, + memory_order_release); + + if (next) + wake_idle_server(); + + result = worker_utls->self; + goto out; + } + + /* + * Get the kernel's idle worker list. + * + * TODO: review whether memory order below can be weakened to + * memory_order_acq_rel. + */ + head = (uint64_t *)atomic_exchange_explicit(&group->idle_workers_head, + 0ULL, memory_order_seq_cst); + + if (!head) + goto out; + + group->idle_workers = head; + goto once_again; + +out: + res = pthread_spin_unlock(&group->idle_worker_lock); + assert(!res); + + return result; +} + +static void enqueue_idle_server(void) +{ + struct umcg_task_tls *server = umcg_task_tls; + struct umcg_group *group = server->group; + int res; + + res = pthread_spin_lock(&group->idle_server_lock); + assert(!res); + + assert(server->next == NULL); + assert((atomic_load_explicit(&server->umcg_task.state_ts, + memory_order_acquire) & + UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_IDLE); + + server->next = group->idle_servers; + group->idle_servers = server; + + res = pthread_spin_unlock(&group->idle_server_lock); + assert(!res); +} + +static umcg_tid idle_server_wait(void) +{ + struct umcg_task_tls *server_utls = umcg_task_tls; + struct umcg_task *server_ut = &umcg_task_tls->umcg_task; + uint32_t server_tid = server_utls->tid; + struct umcg_group *group = umcg_task_tls->group; + umcg_tid worker; + uint32_t prev = 0ULL; + uint64_t state; + bool ok; + + state = atomic_load_explicit(&server_ut->state_ts, memory_order_acquire); + assert((state & UMCG_TASK_STATE_MASK_FULL) == UMCG_TASK_RUNNING); + ok = umcg_update_state(&server_ut->state_ts, &state, UMCG_TASK_IDLE); + assert(ok); + + /* + * Try to become THE idle server that the kernel will wake. + * + * TODO: review whether memory order below can be weakened to + * memory_order_acq_rel for success and memory_order_acquire + * for failure. + */ + ok = atomic_compare_exchange_strong_explicit(&group->idle_server_tid, + &prev, server_tid, + memory_order_seq_cst, memory_order_seq_cst); + + if (!ok) { + assert(prev != server_tid); + enqueue_idle_server(); + umcg_do_wait(0); + assert(server_utls->next == NULL); + + return UMCG_NONE; + } + + /* We need to ensure no idle workers enqueued before going to sleep. */ + worker = get_idle_worker(); + + if (worker) { + state = atomic_load_explicit(&server_ut->state_ts, + memory_order_acquire); + if ((state & UMCG_TASK_STATE_MASK_FULL) != UMCG_TASK_RUNNING) { + ok = umcg_update_state(&server_ut->state_ts, &state, + UMCG_TASK_RUNNING); + assert(ok || ((state & UMCG_TASK_STATE_MASK_FULL) == + UMCG_TASK_RUNNING)); + } + } else + umcg_do_wait(0); + + /* + * If the server calls umcg_get_idle_worker() in a loop, the worker + * that pulled the server at step N (and thus zeroed idle_server_tid) + * may wake the server at step N+1 without cleaning idle_server_tid, + * so the server needs to clean idle_server_tid in case this happens. + * + * TODO: review whether memory order below can be weakened to + * memory_order_acq_rel for success and memory_order_acquire + * for failure. + */ + prev = server_tid; + ok = atomic_compare_exchange_strong_explicit( + &group->idle_server_tid, &prev, 0UL, + memory_order_seq_cst, memory_order_seq_cst); + assert(ok || (prev != server_tid)); + return worker; +} + +umcg_tid umcg_get_idle_worker(bool wait) +{ + umcg_tid result = UMCG_NONE; + + assert(umcg_task_tls->peer == UMCG_NONE); + assert((atomic_load_explicit(&umcg_task_tls->umcg_task.state_ts, + memory_order_acquire) & UMCG_TASK_STATE_MASK_FULL) == + UMCG_TASK_RUNNING); + + do { + result = get_idle_worker(); + + if (result || !wait) + break; + + result = idle_server_wait(); + } while (!result); + + assert((atomic_load_explicit(&umcg_task_tls->umcg_task.state_ts, + memory_order_acquire) & UMCG_TASK_STATE_MASK_FULL) == + UMCG_TASK_RUNNING); + return result; +} diff --git a/tools/lib/umcg/libumcg.h b/tools/lib/umcg/libumcg.h new file mode 100644 index 000000000000..8d97d4032667 --- /dev/null +++ b/tools/lib/umcg/libumcg.h @@ -0,0 +1,299 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#ifndef __LIBUMCG_H +#define __LIBUMCG_H + +#define _GNU_SOURCE +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +/* + * UMCG: User Managed Concurrency Groups. + * + * LIBUMCG provides userspace UMCG API that hides some of the intricacies + * of sys_umcg_ctl() and sys_umcg_wait() syscalls. + * + * Note that this API is still quite low level and is designed as + * a toolkit for building higher-level userspace schedulers. + * + * See tools/lib/umcg/libumcg.txt for detals. + */ + +typedef intptr_t umcg_t; /* UMCG group ID. */ +typedef intptr_t umcg_tid; /* UMCG thread ID. */ + +#define UMCG_NONE (0) + +/** + * umcg_enabled - indicates whether UMCG syscalls are available. + */ +bool umcg_enabled(void); + +/** + * umcg_get_utid - return the UMCG ID of the current thread. + * + * The function always succeeds, and the returned ID is guaranteed to be + * stable over the life of the thread. + * + * The ID is NOT guaranteed to be unique over the life of the process. + */ +umcg_tid umcg_get_utid(void); + +/** + * umcg_set_task_tag - add an arbitrary tag to a registered UMCG task. + * + * Note: not-thread-safe: the user is responsible for proper memory fencing. + */ +void umcg_set_task_tag(umcg_tid utid, intptr_t tag); + +/** + * umcg_get_task_tag - get the task tag. Returns zero if none set. + * + * Note: not-thread-safe: the user is responsible for proper memory fencing. + */ +intptr_t umcg_get_task_tag(umcg_tid utid); + +/** + * enum umcg_create_group_flag - flags to pass to umcg_create_group + * @UMCG_GROUP_ENABLE_PREEMPTION: enable worker preemption. + * + * See tools/lib/libumcg.txt for detals. + */ +enum umcg_create_group_flag { + UMCG_GROUP_ENABLE_PREEMPTION = 1 +}; + +/** + * umcg_create_group - create a UMCG group + * @flags: a combination of values from enum umcg_create_group_flag + * + * See tools/lib/libumcg.txt for detals. + * + * Return: + * UMCG_NONE - an error occurred. Check errno. + * != UMCG_NONE - the ID of the group, to be used in e.g. umcg_register. + */ +umcg_t umcg_create_group(uint32_t flags); + +/** + * umcg_destroy_group - destroy a UMCG group + * @umcg: ID of the group to destroy + * + * The group must be empty (no server or worker threads). + * + * Return: + * 0 - Ok + * -1 - an error occurred. Check errno. + * errno == EAGAIN: the group has server or worker threads + */ +int umcg_destroy_group(umcg_t umcg); + +/** + * umcg_register_basic_task - register the current thread as a UMCG basic task + * @tag: An arbitrary tag to be associated with the task. + * + * See tools/lib/libumcg.txt for detals. + * + * Return: + * UMCG_NONE - an error occurred. Check errno. + * != UMCG_NONE - the ID of the thread to be used with UMCG API (guaranteed + * to match the value returned by umcg_get_utid). + */ +umcg_tid umcg_register_basic_task(intptr_t tag); + +/** + * umcg_register_worker - register the current thread as a UMCG worker + * @group_id: The ID of the UMCG group the thread should join; + * @tag: an arbitrary tag to be associated with the task. + * + * Return: + * UMCG_NONE - an error occurred. Check errno. + * != UMCG_NONE - the ID of the thread to be used with UMCG API (guaranteed + * to match the value returned by umcg_get_utid). + */ +umcg_tid umcg_register_worker(umcg_t group_id, intptr_t tag); + +/** + * umcg_register_server - register the current thread as a UMCG server + * @group_id: The ID of the UMCG group the thread should join; + * @tag: an arbitrary tag to be associated with the task. + * + * Return: + * UMCG_NONE - an error occurred. Check errno. + * != UMCG_NONE - the ID of the thread to be used with UMCG API (guaranteed + * to match the value returned by umcg_get_utid). + */ +umcg_tid umcg_register_server(umcg_t group_id, intptr_t tag); + +/** + * umcg_unregister_task - unregister the current thread. + * + * Return: + * 0 - OK + * -1 - the current thread is not a UMCG thread + */ +int umcg_unregister_task(void); + +/** + * umcg_wait - block the current thread + * @timeout: absolute timeout in nanoseconds + * + * Blocks the current thread, which must have been registered via umcg_register, + * until it is waken via umcg_wake or swapped into via umcg_swap. If the current + * thread has a wakeup queued (see umcg_wake), returns zero immediately, + * consuming the wakeup. + * + * Return: + * 0 - OK, the thread was waken; + * -1 - did not wake normally; + * errno: + * EINTR: interrupted + * EINVAL: some other error occurred + */ +int umcg_wait(uint64_t timeout); + +/** + * umcg_wake - wake @next; non-blocking. + * @next: ID of the thread to wake; + * @wf_current_cpu: an advisory hint indicating that the current thread + * is going to block in the immediate future and that + * the wakee should be woken on the current CPU; + * + * If @next is blocked via umcg_wait or umcg_swap, wake it if @next is + * a server or a basic task; if @next is a worker, it will be queued + * in the idle worker list. If @next is running, queue the wakeup, + * so that a future block of @next will consume the wakeup and will not block. + * + * umcg_wake can queue at most one wakeup; if waking or queueing a wakeup + * is not possible, umcg_wake will SPIN. + * + * See tools/lib/umcg/libumcg.txt for detals. + * + * Return: + * 0 - OK, @next has woken, or a wakeup has been queued; + * -1 - an error occurred. + */ +int umcg_wake(umcg_tid next, bool wf_current_cpu); + +/** + * umcg_swap - wake @next, put the current thread to sleep + * @next: ID of the thread to wake + * @timeout: absolute timeout in ns + * + * umcg_swap is semantically equivalent to + * + * int ret = umcg_wake(next, true); + * if (ret) + * return ret; + * return umcg_wait(timeout); + * + * but may do a synchronous context switch into @next on the current CPU. + * + * Note: if @next is a worker, it must be IDLE, but not in the idle worker list. + * See tools/lib/umcg/libumcg.txt for detals. + */ +int umcg_swap(umcg_tid next, u64 timeout); + +/** + * umcg_get_idle_worker - get an idle worker, if available + * @wait: if true, block until an idle worker becomes available + * + * The current thread must be a UMCG server. If there is a list/queue of + * waiting IDLE workers in the server's group, umcg_get_idle_worker + * picks one; if there are no IDLE workers, the current thread sleeps in + * the idle server queue if @wait is true. + * + * Note: servers waiting for idle workers must NOT be woken via umcg_wake(), + * as this will leave them in inconsistent state. + * + * See tools/lib/umcg/libumcg.txt for detals. + * + * Return: + * UMCG_NONE - an error occurred; check errno; + * != UMCG_NONE - a RUNNABLE worker. + */ +umcg_tid umcg_get_idle_worker(bool wait); + +/** + * umcg_run_worker - run @worker as a UMCG server + * @worker: the ID of a RUNNABLE worker to run + * + * The current thread must be a UMCG "server". + * + * See tools/lib/umcg/libumcg.txt for detals. + * + * Return: + * UMCG_NONE - if errno == 0, the last worker the server was running + * unregistered itself; if errno != 0, an error occurred + * != UMCG_NONE - the ID of the last worker the server was running before + * the worker was blocked or preempted. + */ +umcg_tid umcg_run_worker(umcg_tid worker); + +/** + * umcg_preempt_worker - preempt a RUNNING worker. + * @worker: the ID of a RUNNING worker to preempt. + * + * See tools/lib/umcg/libumcg.txt for detals. + * + * Return: + * 0 - Ok; + * -1 - an error occurred; check errno and `man tgkill()`. In addition + * to tgkill() errors, EAGAIN is also returned if the worker + * is not in RUNNING state (in this case tgkill() was not called). + */ +int umcg_preempt_worker(umcg_tid worker); + +/** + * umcg_get_task_state - return the UMCG state of @task, including state + * flags, without the timestamp. + * + * Note that in most situations the state value can be changed at any time + * by a concurrent thread, so this function is exposed for debugging/testing + * purposes only. + */ +uint64_t umcg_get_task_state(umcg_tid task); + +#ifndef NSEC_PER_SEC +#define NSEC_PER_SEC 1000000000L +#endif + +/** + * umcg_get_time_ns - returns the absolute current time in nanoseconds. + * + * The function uses CLOCK_MONOTONIC; the returned value can be used + * to set absolute timeouts for umcg_wait() and umcg_swap(). + */ +uint64_t umcg_get_time_ns(void); + +/** + * UMCG userspace-only task state flag: wakeup queued. + * + * see umcg_wake() above. + */ +#define UMCG_UTF_WAKEUP_QUEUED (1ULL << 17) + +/** + * UMCG userspace-only task state flag: worker in sys_umcg_wait(). + * + * IDLE workers can be in two substates: + * - waiting in sys_umcg_wait(): in this case UTF_WORKER_IN_WAIT flag is set; + * - waiting in the idle worker list: in this case the flag is not set. + * + * If the worker is IDLE in sys_umcg_wait, umcg_wake() clears the flag + * and adds the worker to the idle worker list. + * + * If the worker is IDLE in the idle worker list, umcg_wake() sets + * the wakeup queued flag. + */ +#define UMCG_UTF_WORKER_IN_WAIT (1ULL << 16) + +#endif /* __LIBUMCG_H */ From patchwork Sun Nov 21 21:20:39 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 12631069 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 10D7EC433F5 for ; Sun, 21 Nov 2021 21:23:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0E7646B0078; Sun, 21 Nov 2021 16:21:02 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 070606B007B; Sun, 21 Nov 2021 16:21:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DB6AD6B007D; Sun, 21 Nov 2021 16:21:01 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0193.hostedemail.com [216.40.44.193]) by kanga.kvack.org (Postfix) with ESMTP id C821A6B0078 for ; Sun, 21 Nov 2021 16:21:01 -0500 (EST) Received: from smtpin10.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay05.hostedemail.com (Postfix) with ESMTP id 7F50F1807FB5A for ; Sun, 21 Nov 2021 21:20:51 +0000 (UTC) X-FDA: 78834207144.10.38E65E1 Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) by imf27.hostedemail.com (Postfix) with ESMTP id D7AB770000B8 for ; Sun, 21 Nov 2021 21:20:49 +0000 (UTC) Received: by mail-pj1-f51.google.com with SMTP id gt5so12196670pjb.1 for ; Sun, 21 Nov 2021 13:20:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=posk.io; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=oKSb/V9pWPXfIUxuyorKDioL/30MA/sUKKbzmiv6cug=; b=FBx4ces6pgRQfxR7MdGqi+/iqyZflIWP1RE7/85bv7qRrtGQ6bEWx6ID4RW2Z+46jI 4HVwPPRIuCwDnhCQNVsgO/vKlD5y14yC9DBnsA4XiykMiShJ9pRziOHLVxJO2zMan20d TFHx3HWNyg8goMdIaGwDYGQho+r4gpwsQXrK5/2+mH3NrcukOJJck48/T+2DZxftJB9w IW48VdXgS+RO1ZNkaRN0Au496gYKvYtCOGEJ35ZZdGz2Ec0dX3NxDzcJkJCcu6qUwl7S 2m/MVMMI8KFi2NcXxxklaV4S7gesR/7TnJIXj7AZ156lklB3lKN34+gx9l+a52Pm19+K TlvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=oKSb/V9pWPXfIUxuyorKDioL/30MA/sUKKbzmiv6cug=; b=dJIcs+QH8yKU3ohUsRRwfcrbv+DtVKEHU32UqsEgUUS5TQTr+kT+0Rc79Kb60AWUyF +0qBjpzvuUor7MUkJanEEWTTvxFyn6WZXQchQEE0sJYptNe1zQCkaidCOZI3T8zSx8Mw ZI4f66BWKvL2riBjAth3KJFPVJlP71l+AEkXKEOqPF8FzwbMvmremi+dISyBexH1qQee vvWczsWaZ4IdSvTMXNKW9+2XK5T+KGR/rNcD1Q6IGg8sA9rGY54VMoUXp4Yb9iHV1kBi nMvHySBnvJ9P2Lvkw1+xbSpMDZrZBSrslMtORwVSLPqYl0m9GiFs6A0Rrt7LbMvX/wym rMGA== X-Gm-Message-State: AOAM530xwUaJw4IExKITfFBQVwuiPw3t4miUstKXwPL1xDDhK2N8pP8Y vBi809zCzUZNVNQdsXAjb1XwQw== X-Google-Smtp-Source: ABdhPJwlOCJU2tOHGk6qbzvyQRuoqHga6jcnnw/D49a7f4SSS318PtqIHkrHbk7ZJrXgMpMXAm2SiA== X-Received: by 2002:a17:902:c202:b0:142:2441:aa25 with SMTP id 2-20020a170902c20200b001422441aa25mr101095996pll.68.1637529649849; Sun, 21 Nov 2021 13:20:49 -0800 (PST) Received: from posk-p1g4.localdomain (23-118-52-46.lightspeed.sntcca.sbcglobal.net. [23.118.52.46]) by smtp.gmail.com with ESMTPSA id k8sm6207924pfu.75.2021.11.21.13.20.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 21 Nov 2021 13:20:49 -0800 (PST) From: Peter Oskolkov X-Google-Original-From: Peter Oskolkov To: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org Cc: Paul Turner , Ben Segall , Peter Oskolkov , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: [PATCH v0.9 5/6] sched/umcg: add Documentation/userspace-api/umcg.txt Date: Sun, 21 Nov 2021 13:20:39 -0800 Message-Id: <20211121212040.8649-6-posk@google.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211121212040.8649-1-posk@google.com> References: <20211121212040.8649-1-posk@google.com> MIME-Version: 1.0 X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: D7AB770000B8 X-Stat-Signature: i1f39feebpwqkef3c7ymfkdj8jx89owq Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=posk.io header.s=google header.b=FBx4ces6; dmarc=none; spf=pass (imf27.hostedemail.com: domain of posk@posk.io designates 209.85.216.51 as permitted sender) smtp.mailfrom=posk@posk.io X-HE-Tag: 1637529649-151398 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Document User Managed Concurrency Groups syscalls, data structures, state transitions, etc. in UMGG kernel API. Signed-off-by: Peter Oskolkov --- Documentation/userspace-api/umcg.txt | 598 +++++++++++++++++++++++++++ 1 file changed, 598 insertions(+) create mode 100644 Documentation/userspace-api/umcg.txt -- 2.25.1 diff --git a/Documentation/userspace-api/umcg.txt b/Documentation/userspace-api/umcg.txt new file mode 100644 index 000000000000..539b7c6a8962 --- /dev/null +++ b/Documentation/userspace-api/umcg.txt @@ -0,0 +1,598 @@ +UMCG API (KERNEL) + +User Managed Concurrency Groups (UMCG) is an M:N threading +subsystem/toolkit that lets user space application developers implement +in-process user space schedulers. + +See tools/lib/umcg/umcg.txt for LIBUMCG API, as opposed to UMCG API (kernel) +described here. The first three subsections are the same in both documents. + + +CONTENTS + + WHY? HETEROGENEOUS IN-PROCESS WORKLOADS + REQUIREMENTS + WHY TWO APIS: UMCG (KERNEL) AND LIBUMCG (USERSPACE)? + UMCG API (KERNEL) + SERVERS + WORKERS + UMCG TASK STATES + STRUCT UMCG_TASK + SYS_UMCG_CTL() + SYS_UMCG_WAIT() + STATE TRANSITIONS + SERVER-ONLY USE CASES + + +WHY? HETEROGENEOUS IN-PROCESS WORKLOADS + +Linux kernel's CFS scheduler is designed for the "common" use case, with +efficiency/throughput in mind. Work isolation and workloads of different +"urgency" are addressed by tools such as cgroups, CPU affinity, priorities, +etc., which are difficult or impossible to efficiently use in-process. + +For example, a single DBMS process may receive tens of thousands requests +per second; some of these requests may have strong response latency +requirements as they serve live user requests (e.g. login authentication); +some of these requests may not care much about latency but must be served +within a certain time period (e.g. an hourly aggregate usage report); some +of these requests are to be served only on a best-effort basis and can be +NACKed under high load (e.g. an exploratory research/hypothesis testing +workload). + +Beyond different work item latency/throughput requirements as outlined +above, the DBMS may need to provide certain guarantees to different users; +for example, user A may "reserve" 1 CPU for their high-priority/low-latency +requests, 2 CPUs for mid-level throughput workloads, and be allowed to send +as many best-effort requests as possible, which may or may not be served, +depending on the DBMS load. Besides, the best-effort work, started when the +load was low, may need to be delayed if suddenly a large amount of +higher-priority work arrives. With hundreds or thousands of users like +this, it is very difficult to guarantee the application's responsiveness +using standard Linux tools while maintaining high CPU utilization. + +Gaming is another use case: some in-process work must be completed before a +certain deadline dictated by frame rendering schedule, while other work +items can be delayed; some work may need to be cancelled/discarded because +the deadline has passed; etc. + +User Managed Concurrency Groups is an M:N threading toolkit that allows +constructing user space schedulers designed to efficiently manage +heterogeneous in-process workloads described above while maintaining high +CPU utilization (95%+). + + +REQUIREMENTS + +One relatively established way to design high-efficiency, low-latency +systems is to split all work into small on-cpu work items, with +asynchronous I/O and continuations, all executed on a thread pool with the +number of threads not exceeding the number of available CPUs. Although this +approach works, it is quite difficult to develop and maintain such a +system, as, for example, small continuations are difficult to piece +together when debugging. Besides, such asynchronous callback-based systems +tend to be somewhat cache-inefficient, as continuations can get scheduled +on any CPU regardless of cache locality. + +M:N threading and cooperative user space scheduling enables controlled CPU +usage (minimal OS preemption), synchronous coding style, and better cache +locality. + +Specifically: + +* a variable/fluctuating number M of "application" threads should be + "scheduled over" a relatively fixed number N of "kernel" threads, where + N is less than or equal to the number of CPUs available; +* only those application threads that are attached to kernel threads are + scheduled "on CPU"; +* application threads should be able to cooperatively yield to each other; +* when an application thread blocks in kernel (e.g. in I/O), this becomes + a scheduling event ("block") that the userspace scheduler should be able + to efficiently detect, and reassign a waiting application thread to the + freeded "kernel" thread; +* when a blocked application thread wakes (e.g. its I/O operation + completes), this event ("wake") should also be detectable by the + userspace scheduler, which should be able to either quickly dispatch the + newly woken thread to an idle "kernel" thread or, if all "kernel" + threads are busy, put it in the waiting queue; +* in addition to the above, it would be extremely useful for a separate + in-process "watchdog" facility to be able to monitor the state of each + of the M+N threads, and to intervene in case of runaway workloads + (interrupt/preempt). + + +WHY THE TWO APIS: UMCG (KERNEL) AND LIBUMCG (USERSPACE)? + +UMCG syscalls, sys_umcg_ctl() and sys_umcg_wait(), are designed to make +the kernel-side UMCG implementation as lightweight as possible. LIBUMCG, +on the other hand, is designed to expose the key abstractions to users +in a much more usable, higher-level way. + +See tools/lib/umcg/libumcg.txt for more details on LIBUMCG API. + + +UMCG API (KERNEL) + +Based on the requrements above, UMCG API (kernel) is build around the +following ideas: + +* UMCG server: a task/thread representing "kernel threads", or CPUs from + the requirements above; +* UMCG worker: a task/thread representing "application threads", to be + scheduled over servers; +* UMCG task state: (NONE), RUNNING, BLOCKED, IDLE: states a UMCG task (a + server or a worker) can be in; +* UMCG task state flag: LOCKED, PREEMPTED: additional state flags that + can be ORed with the task state to communicate additional information to + the kernel; +* struct umcg_task: a per-task userspace set of data fields, usually + residing in the TLS, that fully reflects the current task's UMCG state + and controls the way the kernel manages the task; +* sys_umcg_ctl(): a syscall used to register the current task/thread as a + server or a worker, or to unregister a UMCG task; +* sys_umcg_wait(): a syscall used to put the current task to sleep and/or + wake another task, pontentially context-switching between the two tasks + on-CPU synchronously. + + +SERVERS + +When a task/thread is registered as a server, it is in RUNNING state and +behaves like any other normal task/thread. In addition, servers can +interact with other UMCG tasks via sys_umcg_wait(): + +* servers can voluntarily suspend their execution (wait), becoming IDLE; +* servers can wake other IDLE servers; +* servers can context-switch between each other. + +Note that if a server blocks in the kernel not via sys_umcg_wait(), it +still retains its RUNNING state. + + +WORKERS + +A worker cannot be RUNNING without having a server associated with it, so +when a task is first registered as a worker, it enters the IDLE state. + +* a worker becomes RUNNING when a server calls sys_umcg_wait to + context-switch into it; the server goes IDLE, and the worker becomes + RUNNING in its place; +* when a RUNNING worker blocks in the kernel, it becomes BLOCKED, its + associated server becomes RUNNING and the server's sys_umcg_wait() call + from the bullet above returns; this transition is sometimes called + "block detection"; +* when the syscall on which a BLOCKED worker completes, the worker + becomes IDLE and is added to the list of idle workers; if there is an + idle server waiting, the kernel wakes it; this transition is sometimes + called "wake detection"; +* RUNNING workers can voluntarily suspend their execution (wait), + becoming IDLE; their associated servers are woken; +* a RUNNING worker can context-switch with an IDLE worker; the server of + the switched-out worker is transferred to the switched-in worker; +* any UMCG task can "wake" an IDLE worker via sys_umcg_wait(); unless + this is a server running the worker as described in the first bullet in + this list, the worker remain IDLE but is added to the idle workers list; + this "wake" operation exists for completeness, to make sure + wait/wake/context-switch operations are available for all UMCG tasks; +* the userspace can preempt a RUNNING worker by marking it + RUNNING|PREEMPTED and sending a signal to it; the userspace should have + installed a NOP signal handler for the signal; the kernel will then + transition the worker into IDLE|PREEMPTED state and wake its associated + server. + + +UMCG TASK STATES + +Important: all state transitions described below involve at least two +steps: the change of the state field in struct umcg_task, for example +RUNNING to IDLE, and the corresponding change in struct task_struct state, +for example a transition between the task running on CPU and being +descheduled and removed from the kernel runqueue. The key principle of UMCG +API design is that the party initiating the state transition modifies the +state variable. + +For example, a task going IDLE first changes its state from RUNNING to IDLE +in the userpace and then calls sys_umcg_wait(), which completes the +transition. + +Note on documentation: in include/uapi/linux/umcg.h, task states have the +form UMCG_TASK_RUNNING, UMCG_TASK_BLOCKED, etc. In this document these are +usually referred to simply RUNNING and BLOCKED, unless it creates +ambiguity. Task state flags, e.g. UMCG_TF_PREEMPTED, are treated similarly. + +UMCG task states reflect the view from the userspace, rather than from the +kernel. There are three fundamental task states: + +* RUNNING: indicates that the task is schedulable by the kernel; applies + to both servers and workers; +* IDLE: indicates that the task is not schedulable by the kernel (see + umcg_idle_loop() in kernel/sched/umcg.c); applies to both servers and + workers; +* BLOCKED: indicates that the worker is blocked in the kernel; does not + apply to servers. + +In addition to the three states above, two state flags help with state +transitions: + +* LOCKED: the userspace is preparing the worker for a state transition + and "locks" the worker until the worker is ready for the kernel to act + on the state transition; used similarly to preempt_disable or + irq_disable in the kernel; applies only to workers in RUNNING or IDLE + state; RUNNING|LOCKED means "this worker is about to become RUNNING, + while IDLE|LOCKED means "this worker is about to become IDLE or + unregister; +* PREEMPTED: the userspace indicates it wants the worker to be preempted; + there are no situations when both LOCKED and PREEMPTED flags are set at + the same time. + + +STRUCT UMCG_TASK + +From include/uapi/linux/umcg.h: + +struct umcg_task { + uint64_t state_ts; /* r/w */ + uint32_t next_tid; /* r */ + uint32_t flags; /* reserved */ + uint64_t idle_workers_ptr; /* r/w */ + uint64_t idle_server_tid_ptr; /* r* */ +}; + +Each UMCG task is identified by struct umcg_task, which is provided to the +kernel when the task is registered via sys_umcg_ctl(). + +* uint64_t state_ts: the current state of the task this struct + identifies, as described in the previous section, combined with a + unique timestamp indicating when the last state change happened. + + Readable/writable by both the kernel and the userspace. + + bits 0 - 5: task state (RUNNING, IDLE, BLOCKED); + bits 6 - 7: state flags (LOCKED, PREEMPTED); + bits 8 - 12: reserved; must be zeroes; + bits 13 - 17: for userspace use; + bits 18 - 63: timestamp. + + Timestamp: a 46-bit CLOCK_MONOTONIC timestamp, at 16ns resolution. + + It is highly benefitical to tag each state change with a unique + timestamp: + + - timestamps will naturally provide instrumentation to measure + scheduling delays, both in the kernel and in the userspace; + - uniqueness of timestamps (module overflow) guarantees that state + change races, especially ABA races, are easily detected and avoided. + + Each timestamp represents the moment in time the state change happened, + in nanoseconds, with the lower 4 bits and the upper 16 bits stripped. + + In this document 'umcg_task.state' is often used to talk about + 'umcg_task.state_ts' field, as timestamps do not carry semantic + meaning at the moment. + + This is how umcg_task.state_ts is updated in the kernel: + + /* kernel side */ + /** + * umcg_update_state: atomically update umcg_task.state_ts, set new timestamp. + * @state_ts - points to the state_ts member of struct umcg_task to update; + * @expected - the expected value of state_ts, including the timestamp; + * @desired - the desired value of state_ts, state part only; + * @may_fault - whether to use normal or _nofault cmpxchg. + * + * The function is basically cmpxchg(state_ts, expected, desired), with extra + * code to set the timestamp in @desired. + */ + static int umcg_update_state(u64 __user *state_ts, u64 *expected, u64 desired, + bool may_fault) + { + u64 curr_ts = (*expected) >> (64 - UMCG_STATE_TIMESTAMP_BITS); + u64 next_ts = ktime_get_ns() >> UMCG_STATE_TIMESTAMP_GRANULARITY; + + /* Cut higher order bits. */ + next_ts &= ((1ULL << UMCG_STATE_TIMESTAMP_BITS) - 1); + + if (next_ts == curr_ts) + ++next_ts; + + /* Remove an old timestamp, if any. */ + desired &= ((1ULL << (64 - UMCG_STATE_TIMESTAMP_BITS)) - 1); + + /* Set the new timestamp. */ + desired |= (next_ts << (64 - UMCG_STATE_TIMESTAMP_BITS)); + + if (may_fault) + return cmpxchg_user_64(state_ts, expected, desired); + + return cmpxchg_user_64_nofault(state_ts, expected, desired); + } + +* uint32_t next_tid: contains the TID of the task to context-switch-into + in sys_umcg_wait(); can be zero; writable by the userspace, readable by + the kernel; if this is a RUNNING worker, this field contains the TID of + the server that should be woken when this worker blocks; see + sys_umcg_wait() for more details; + +* uint32_t flags: reserved; must be zero. + +* uint64_t idle_workers_ptr: this field forms a single-linked list of + idle workers: all RUNNING workers have this field set to point to the + head of the list (a pointer variable in the userspace). + + When a worker's blocking operation in the kernel completes, the kernel + changes the worker's state from BLOCKED to IDLE and adds the worker to + the top of the list of idle workers using this logic: + + /* kernel side */ + /** + * enqueue_idle_worker - push an idle worker onto idle_workers_ptr + * list/stack. + * + * Returns true on success, false on a fatal failure. + */ + static bool enqueue_idle_worker(struct umcg_task __user *ut_worker) + { + u64 __user *node = &ut_worker->idle_workers_ptr; + u64 __user *head_ptr; + u64 first = (u64)node; + u64 head; + + if (get_user_nosleep(head, node) || !head) + return false; + + head_ptr = (u64 __user *)head; + + if (put_user_nosleep(UMCG_IDLE_NODE_PENDING, node)) + return false; + + if (xchg_user_64(head_ptr, &first)) + return false; + + if (put_user_nosleep(first, node)) + return false; + + return true; + } + + In the userspace the list is cleared atomically using this logic: + + /* userspace side */ + uint64_t *idle_workers = (uint64_t *)*head; + + atomic_exchange(&idle_workers, NULL); + + The userspace re-points workers' idle_workers_ptr to the list head + variable before the worker is allowed to become RUNNING again. + + When processing the idle workers list, the userspace should wait for + workers marked as UMCG_IDLE_NODE_PENDING to have the flag cleared (see + enqueue_idle_worker() above). + +* uint64_t idle_server_tid_ptr: points to a variable in the userspace + that points to an idle server, i.e. a server in IDLE state waiting in + sys_umcg_wait(); read-only; workers must have this field set; not used + in servers. + + When a worker's blocking operation in the kernel completes, the kernel + changes the worker's state from BLOCKED to IDLE, adds the worker to the + list of idle workers, and wakes the idle server if present; the kernel + atomically exchanges (*idle_server_tid_ptr) with 0, thus waking the idle + server, if present, only once. See State transitions below for more + details. + + +SYS_UMCG_CTL() + +int sys_umcg_ctl(uint32_t flags, struct umcg_task *self) is used to +register or unregister the current task as a worker or server. Flags can be +one of the following: + + UMCG_CTL_REGISTER: register a server; + UMCG_CTL_REGISTER | UMCG_CTL_WORKER: register a worker; + UMCG_CTL_UNREGISTER: unregister the current server or worker. + +When registering a task, self must point to struct umcg_task describing +this server or worker; the pointer must remain valid until the task is +unregistered. + +When registering a server, self->state must be RUNNING; all other fields in +self must be zeroes. + +When registering a worker, self->state must be BLOCKED; +self->idle_server_tid_ptr and self->idle_workers_ptr must be valid pointers +as described in struct umcg_task; self->next_tid must be zero. + +When unregistering a task, self must be NULL. + + +SYS_UMCG_WAIT() + +int sys_umcg_wait(uint32_t flags, uint64_t abs_timeout) operates on +registered UMCG servers and workers: struct umcg_task *self provided to +sys_umcg_ctl() when registering the current task is consulted in addition +to flags and abs_timeout parameters. + +The function can be used to perform one of the three operations: + +* wait: if self->next_tid is zero, sys_umcg_wait() puts the current + task to sleep; +* wake: if self->next_tid is not zero, and flags & UMCG_WAIT_WAKE_ONLY, + the task identified by next_tid is woken; +* context switch: if self->next_tid is not zero, and !(flags & + UMCG_WAIT_WAKE_ONLY), the current task is put to sleep and the next task + is woken, synchronously switching between the tasks on the current CPU + on the fast path. + +Flags can be zero or a combination of the following values: + +* UMCG_WAIT_WAKE_ONLY: wake the next task, don't put the current task to + sleep; +* UMCG_WAIT_WF_CURRENT_CPU: wake the next task on the curent CPU; this + flag has an effect only if UMCG_WAIT_WAKE_ONLY is set: context switching + is always attempted to happen on the curent CPU. + +The section below provides more details on how servers and workers interact +via sys_umcg_wait(), during worker block/wake events, and during worker +preemption. + + +STATE TRANSITIONS + +As mentioned above, the key principle of UMCG state transitions is that the +party initiating the state transition modifies the state of affected tasks. + +Below, "TASK:STATE" indicates a task T, where T can be either W for worker +or S for server, in state S, where S can be one of the three states, +potentially ORed with a state flag. Each individual state transition is an +atomic operation (cmpxchg) unless indicated otherwise. Also note that the +order of state transitions is important and is part of the contract between +the userspace and the kernel. The kernel is free to kill the task (SIGKILL) +if the contract is broken. + +Some worker state transitions below include adding LOCKED flag to worker +state. This is done to indicate to the kernel that the worker is +transitioning state and should not participate in the block/wake detection +routines, which can happen due to interrupts/pagefaults/signals. + +IDLE|LOCKED means that a running worker is preparing to sleep, so +interrupts should not lead to server wakeup; RUNNING|LOCKED means that an +idle worker is going to be "scheduled to run", but may not yet have its +server set up properly. + +The key invariant: a RUNNING worker (not LOCKED) must have a server +assigned to it. + +Key state transitions: + +* server to worker context switch ("schedule a worker to run"): + S:RUNNING+W:IDLE => S:IDLE+W:RUNNING: + in the userspace, in the context of the server S running: + S:RUNNING => S:IDLE (mark self as idle) + W:IDLE => W:RUNNING|LOCKED (mark the worker as running) + W.next_tid := S.tid; S.next_tid := W.tid (link the server with + the worker) + W:RUNNING|LOCKED => W:RUNNING (unlock the worker) + S: sys_umcg_wait() (make the syscall) + the kernel context switches from the server to the worker; the + server sleeps until it becomes RUNNING during one of the + transitions below; + +* worker to server context switch (worker "yields"): S:IDLE+W:RUNNING => +S:RUNNING+W:IDLE: + in the userspace, in the context of the worker W running (note that + a running worker has its next_tid set to point to its server): + W:RUNNING => W:IDLE|LOCKED (mark self as idle) + S:IDLE => S:RUNNING (mark the server as running) + W: sys_umcg_wait() (make the syscall) + the kernel removes the LOCKED flag from the worker's state and + context switches from the worker to the server; the worker sleeps + until it becomes RUNNING; + +* worker to worker context switch: W1:RUNNING+W2:IDLE => + W1:IDLE+W2:RUNNING: + in the userspace, in the context of W1 running: + W2:IDLE => W2:RUNNING|LOCKED (mark W2 as running) + W1:RUNNING => W1:IDLE|LOCKED (mark self as idle) + W2.next_tid := W1.next_tid; S.next_tid := W2.tid (transfer the + server W1 => W2) + W1:next_tid := W2.tid (indicate that W1 should context-switch + into W2) + W2:RUNNING|LOCKED => W2:RUNNING (unlock W2) + W1: sys_umcg_wait() (make the syscall) + same as above, the kernel removes the LOCKED flag from the W1's + state and context switches to next_tid; + +* worker wakeup: W:IDLE => W:IDLE, W queued into the idle worker list: + in the userspace, a server S can wake a worker W sleeping in + sys_umcg_wait() without "running" it. This is a purely + userspace operation that adds the worker to the idle worker list. + +* block detection: worker blocks in the kernel: S:IDLE+W:RUNNING => + S:RUNNING+W:BLOCKED: + when a worker blocks in the kernel in RUNNING state (not LOCKED), + before descheduling the task from the CPU the kernel performs + these operations: + W:RUNNING => W:BLOCKED + S := W.next_tid + S:IDLE => S:RUNNING + try_to_wake_up(S) + if any of the first three operations above fail, the worker is + killed via SIGKILL. Note that ttwu(S) is not required to succeed, + as the server may still be transitioning to sleep in + sys_umcg_wait(); before actually putting the server to sleep its + UMCG state is checked and, if it is RUNNING, sys_umcg_wait() + returns to the userspace; + if the worker has its LOCKED flag set, block detection does not + trigger, as the worker is assumed to be in the userspace + scheduling code. + +* wake detection: worker wakes in the kernel: W:BLOCKED => W:IDLE: + all workers' returns to the userspace are intercepted: + start: (a label) + if W:RUNNING & W.next_tid != 0: let the worker exit to the + userspace, as this is a RUNNING worker with a server; + W:* => W:IDLE (previously blocked or woken without servers + workers are not allowed to return to the userspace); + the worker is appended to W.idle_workers_ptr idle workers list; + S := *W.idle_server_tid_ptr; if (S != 0) S:IDLE => S.RUNNING; + ttwu(S) + idle_loop(W): this is the same idle loop that sys_umcg_wait() + uses: it breaks only when the worker becomes RUNNING; when + the idle loop exits, it is assumed that the userspace has + properly removed the worker from the idle workers list + before marking it RUNNING; + goto start; (repeat from the beginning). + + the logic above is a bit more complicated in the presence of + LOCKED or PREEMPTED flags, but the main invariants + stay the same: + only RUNNING workers with servers assigned are allowed to run + in the userspace (unless LOCKED); + newly IDLE workers are added to the idle workers list; any + user-initiated state change assumes the userspace + properly removed the worker from the list; + as with wake detection, any "breach of contract" by the + userspace will result in the task termination via SIGKILL. + +* worker preemption: S:IDLE+W:RUNNING => S:RUNNING+W:IDLE|PREEMPTED: + when the userspace wants to preempt a RUNNING worker, it changes it + state, atomically, RUNNING => RUNNING|PREEMPTED and sends a + signal to the worker via tgkill(); the signal handler, previously + set up by the userspace, can be a NOP (note that only RUNNING + workers can be preempted); + + if the worker, at the moment the signal arrived, continued to be + running on-CPU in the userspace, the "wake detection" code will be + triggered that, in addition to what was described above, will + check if the worker is in RUNNING|PREEMPTED state: + W:RUNNING|PREEMPTED => W:IDLE|PREEMPTED + S := W.next_tid + S:IDLE => S:RUNNING + try_to_wakeup(S) + + if the signal arrives after the worker blocks in the kernel, + the "block detection" happened as described above, with the + following change: + W:RUNNING|PREEMPTED => W:BLOCKED|PREEMPTED + S := W.next_tid + S:IDLE => S:RUNNING + try_to_wake_up(S) + + in any case, the worker's server is woken, with its attached + worker (S.next_tid) either in BLOCKED|PREEMPTED or IDLE|PREEMPTED + state. + + +SERVER-ONLY USE CASES + +Some workloads/applications may benefit from fast and synchronous on-CPU +user-initiated context switches without the need for full userspace +scheduling (block/wake detection). These applications can use "standalone" +UMCG servers to wait/wake/context-switch. At the moment only in-process +operations are allowed. In the future this restriction will be lifted, +and wait/wake/context-switch operations between servers in related processes +be permitted (when it is safe to do so, e.g. if the processes belong +to the same user and/or cgroup). + +These "worker-less" operations involve trivial RUNNING <==> IDLE state +changes, not discussed here for brevity. From patchwork Sun Nov 21 21:20:40 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 12631071 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5BBE9C433FE for ; Sun, 21 Nov 2021 21:24:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 072306B007B; Sun, 21 Nov 2021 16:21:03 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F3C0B6B007D; Sun, 21 Nov 2021 16:21:02 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D8E556B007E; Sun, 21 Nov 2021 16:21:02 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0192.hostedemail.com [216.40.44.192]) by kanga.kvack.org (Postfix) with ESMTP id C657D6B007B for ; Sun, 21 Nov 2021 16:21:02 -0500 (EST) Received: from smtpin01.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with ESMTP id 909028B76A for ; Sun, 21 Nov 2021 21:20:52 +0000 (UTC) X-FDA: 78834207228.01.916CB36 Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) by imf23.hostedemail.com (Postfix) with ESMTP id AF6BD900038C for ; Sun, 21 Nov 2021 21:20:48 +0000 (UTC) Received: by mail-pj1-f50.google.com with SMTP id nh10-20020a17090b364a00b001a69adad5ebso13524684pjb.2 for ; Sun, 21 Nov 2021 13:20:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=posk.io; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=B00tJn5rnYuWYSpk3zTcunA3N+4r514ND/7t0xIcXv8=; b=hAUGZAkecdJy36k9sN9KoMAzCmdHEc36JnRSpCpwQAkexWrtZ0YnSaBh3mlhBjGazH OIKAoyMOlvpQF5Q4XcToMKVx+J8kZiC5+nM9eaezaXFWa0p2nv5fH3oE7HZRSstsa4Ft 0IlTLZb/ueYspTiP69z0rdiDZt97dnCEx7REA56cb9dGJkMPkDh0UofMFLQceBU8w5iM 7nStrlDtwZd2Iju4bUjC6vsmSdTSlhPVf22AfWpvmOtWMBYbykjQSYdtTsl9iTii1byU KOA/zfHleTszM751UED0FGgOBaXk016cfROIAbRziAnJBqfx2s1S1RSY3pYCkckxGTBJ 4P0A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=B00tJn5rnYuWYSpk3zTcunA3N+4r514ND/7t0xIcXv8=; b=lZVR5Hx9IYeDiJKlyCNP9jcLLJ/5bocF9RK1A9PXVwSEtmavU52hYcrYs5CRbVohh2 1TbDsAEY1GMR9ViMCnicRqK7VlIb9C5EbHb8AagE+Hq4TkWF7Ee2WVAnWfCDTPxHXkfe NuC4FdmzP0wcSBe5YSa5nW9pecKxMue56tXCkCAYv1LsKr8BeLJmPdflTlSa5YgjBqWb yLB+yyyk/Q1qV41ndiWjZHs9iYb6xV8umhKjQEUZ++q07+TU9ffREwzTQVDn32dUXKrF qpbxIOw7ULW33G6TOFv1OfiAO1JNGlwJw3OvMuT011DU7x/93F5t9DYXR5y2WFUz8Kez Kgeg== X-Gm-Message-State: AOAM531lfv45afvCDlbIetV2llIOBgFV5IjsiV9yfYuRw44opV2NN21v MpttAgPp5GP2D6ZEcW7496Eh2g== X-Google-Smtp-Source: ABdhPJy2JNkkge0i57TNUZBlu99WACVnMnpaLyoEWYO3xubRJLBQRyKGiJXu+K4ZWB1pl9GeoZaUQQ== X-Received: by 2002:a17:90b:4a43:: with SMTP id lb3mr24617763pjb.222.1637529651048; Sun, 21 Nov 2021 13:20:51 -0800 (PST) Received: from posk-p1g4.localdomain (23-118-52-46.lightspeed.sntcca.sbcglobal.net. [23.118.52.46]) by smtp.gmail.com with ESMTPSA id k8sm6207924pfu.75.2021.11.21.13.20.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 21 Nov 2021 13:20:50 -0800 (PST) From: Peter Oskolkov X-Google-Original-From: Peter Oskolkov To: Peter Zijlstra , Ingo Molnar , Thomas Gleixner , Andrew Morton , Dave Hansen , Andy Lutomirski , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-api@vger.kernel.org Cc: Paul Turner , Ben Segall , Peter Oskolkov , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: [PATCH v0.9 6/6] sched/umcg, lib/umcg: add tools/lib/umcg/libumcg.txt Date: Sun, 21 Nov 2021 13:20:40 -0800 Message-Id: <20211121212040.8649-7-posk@google.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20211121212040.8649-1-posk@google.com> References: <20211121212040.8649-1-posk@google.com> MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: AF6BD900038C X-Stat-Signature: dhghqit5uqyzdeo3sgcxxw543przep8n Authentication-Results: imf23.hostedemail.com; dkim=pass header.d=posk.io header.s=google header.b=hAUGZAke; dmarc=none; spf=pass (imf23.hostedemail.com: domain of posk@posk.io designates 209.85.216.50 as permitted sender) smtp.mailfrom=posk@posk.io X-HE-Tag: 1637529648-903913 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Document libumcg. Signed-off-by: Peter Oskolkov --- tools/lib/umcg/libumcg.txt | 438 +++++++++++++++++++++++++++++++++++++ 1 file changed, 438 insertions(+) create mode 100644 tools/lib/umcg/libumcg.txt -- 2.25.1 diff --git a/tools/lib/umcg/libumcg.txt b/tools/lib/umcg/libumcg.txt new file mode 100644 index 000000000000..06f509bf5341 --- /dev/null +++ b/tools/lib/umcg/libumcg.txt @@ -0,0 +1,438 @@ +LIBUMCG API (USERSPACE) + +User Managed Concurrency Groups (UMCG) is an M:N threading +subsystem/toolkit that lets user space application developers implement +in-process user space schedulers. + +See Documentation/userspace-api/umcg.txt for UMCG API (kernel), as opposed +to LIBUMCG API described here. The first three subsections are the +same in both documents. + + +CONTENTS + + WHY? HETEROGENEOUS IN-PROCESS WORKLOADS + REQUIREMENTS + WHY THE TWO APIS: UMCG (KERNEL) AND LIBUMCG (USERSPACE)? + LIBUMCG API (USERSPACE) + SERVERS + WORKERS + BASIC UMCG TASKS + LIBUMCG API + umcg_t + umcg_tid + UMCG_NONE + umcg_enabled() + umcg_get_utid() + umcg_set_task_tag() + umcg_get_task_tag() + umcg_create_group() + umcg_destroy_group() + umcg_register_basic_task() + umcg_register_worker() + umcg_register_server() + umcg_unregister_task() + umcg_wait() + umcg_wake() + umcg_swap() + umcg_get_idle_worker() + umcg_run_worker() + umcg_preempt_worker() + umcg_get_time_ns() + + +WHY? HETEROGENEOUS IN-PROCESS WORKLOADS + +Linux kernel's CFS scheduler is designed for the "common" use case, with +efficiency/throughput in mind. Work isolation and workloads of different +"urgency" are addressed by tools such as cgroups, CPU affinity, priorities, +etc., which are difficult or impossible to efficiently use in-process. + +For example, a single DBMS process may receive tens of thousands requests +per second; some of these requests may have strong response latency +requirements as they serve live user requests (e.g. login authentication); +some of these requests may not care much about latency but must be served +within a certain time period (e.g. an hourly aggregate usage report); some +of these requests are to be served only on a best-effort basis and can be +NACKed under high load (e.g. an exploratory research/hypothesis testing +workload). + +Beyond different work item latency/throughput requirements as outlined +above, the DBMS may need to provide certain guarantees to different users; +for example, user A may "reserve" 1 CPU for their high-priority/low-latency +requests, 2 CPUs for mid-level throughput workloads, and be allowed to send +as many best-effort requests as possible, which may or may not be served, +depending on the DBMS load. Besides, the best-effort work, started when the +load was low, may need to be delayed if suddenly a large amount of +higher-priority work arrives. With hundreds or thousands of users like +this, it is very difficult to guarantee the application's responsiveness +using standard Linux tools while maintaining high CPU utilization. + +Gaming is another use case: some in-process work must be completed before a +certain deadline dictated by frame rendering schedule, while other work +items can be delayed; some work may need to be cancelled/discarded because +the deadline has passed; etc. + +User Managed Concurrency Groups is an M:N threading toolkit that allows +constructing user space schedulers designed to efficiently manage +heterogeneous in-process workloads described above while maintaining high +CPU utilization (95%+). + + +REQUIREMENTS + +One relatively established way to design high-efficiency, low-latency +systems is to split all work into small on-cpu work items, with +asynchronous I/O and continuations, all executed on a thread pool with the +number of threads not exceeding the number of available CPUs. Although this +approach works, it is quite difficult to develop and maintain such a +system, as, for example, small continuations are difficult to piece +together when debugging. Besides, such asynchronous callback-based systems +tend to be somewhat cache-inefficient, as continuations can get scheduled +on any CPU regardless of cache locality. + +M:N threading and cooperative user space scheduling enables controlled CPU +usage (minimal OS preemption), synchronous coding style, and better cache +locality. + +Specifically: + +* a variable/fluctuating number M of "application" threads should be + "scheduled over" a relatively fixed number N of "kernel" threads, where + N is less than or equal to the number of CPUs available; +* only those application threads that are attached to kernel threads are + scheduled "on CPU"; +* application threads should be able to cooperatively yield to each other; +* when an application thread blocks in kernel (e.g. in I/O), this becomes + a scheduling event ("block") that the userspace scheduler should be able + to efficiently detect, and reassign a waiting application thread to the + freeded "kernel" thread; +* when a blocked application thread wakes (e.g. its I/O operation + completes), this event ("wake") should also be detectable by the + userspace scheduler, which should be able to either quickly dispatch the + newly woken thread to an idle "kernel" thread or, if all "kernel" + threads are busy, put it in the waiting queue; +* in addition to the above, it would be extremely useful for a separate + in-process "watchdog" facility to be able to monitor the state of each + of the M+N threads, and to intervene in case of runaway workloads + (interrupt/preempt). + + +WHY THE TWO APIS: UMCG (KERNEL) AND LIBUMCG (USERSPACE)? + +UMCG syscalls, sys_umcg_ctl() and sys_umcg_wait(), are designed to make +the kernel-side UMCG implementation as lightweight as possible. LIBUMCG, +on the other hand, is designed to expose the key abstractions to users +in a much more usable, higher-level way. + +See Documentation/userspace-api/umcg.txt for more details on +UMCG API (kernel). + +Please note that LIBUMCG API is itself a rather low-level API intended +to be used to construct higher-level userspace schedulers. + +Note: to avoid confusion, in this document "UMCG servers/workers" refer +UMCG tasks when considered in the context of the kernel UMCG API (syscalls), +while "LIBUMCG servers/workers" refer to the same tasks when considered +in the context of the userspace LIBUMC API outlined below. When the +distinction is not important, "UMCG servers/workers" is used generically. + + +LIBUMCG API (USERSPACE) + +Based on the requrements above, LIBUMCG API (userspace) is build around the +following ideas: + +* UMCG server: a thread representing "kernel threads", or CPUs from + the requirements above; +* UMCG worker: a thread representing "application threads", to be + scheduled over servers; +* UMCG group: a collection of servers and workers that can interact with + each other; a single process may contain several UMCG groups (e.g. a + group per NUMA node); +* a set of functions (API) that allows workers to be "scheduled" over + servers and to interact with one another cooperatively. + + +LIBUMCG SERVERS + +When a thread is registered as a server, it behaves like any other normal +thread. + +Servers can interact with other servers in the same UMCG group: + +* servers can voluntarily suspend their execution by calling umcg_wait(); +* servers can wake other servers by calling umcg_wake(); +* servers can context-switch between each other by calling umcg_swap(). + +Servers can also interact with workers in their UMCG group: + +* servers can schedule ("run") workers in their place by calling + umcg_run_worker(); when the worker blocks, the function returns; +* servers can query for workers that finished their blocking operations + by calling umcg_get_idle_worker(); +* servers can force running workers into idle state and have the + servers running those workers to wakeup by calling umcg_preempt_worker(). + + +LIBUMCG WORKERS + +A worker cannot be running without having a server associated with it, so +when a task is first registered as a worker, it is blocked until a server +"runs" it (new workers are added to the idle worker list). + +Workers can interact with other workers in their UMCG group: + +* workers can voluntarily suspend their execution by calling umcg_wait(); +* workers can wake other workers by calling umcg_wake(); +* workers can context-switch between each other by calling umcg_swap(). + + +LIBUMCG BASIC UMCG TASKS + +If the application is only interested in server-to-server interactions, +it does not need to create a UMCG group and may register a server as a +"basic UMCG task". Same umcg_[wait|wake|swap] functions are available. + + +LIBUMCG API: umcg_t + +umcg_t is an opaque pointer indicating a UMCG group. + + +LIBUMCG API: umcg_tid + +umcg_tid is an opaque pointer indicating a UMCG task (a basic task, +a server, or a worker). + + +LIBUMCG API: UMCG_NONE + +UMCG_NONE holds a NULL value for variables of type umcg_t or umcg_tid. + + +LIBUMCG API: umcg_enabled() + +bool umcg_enabled(void) - returns true if the running kernel exposes + UMCG kernel API (sys_umcg_ctl and sys_umcg_wait). + + +LIBUMCG API: umcg_get_utid + +umcg_tid umcg_get_utid(void) - returns the umcg_tid value identifying + the current thread as a UMCG task. The value + is guaranteed to be stable over the life + of the thread, but may be reused between + different threads (it is a pointer to a TLS + variable). + + +LIBUMCG API: umg_set_task_tag() + +void umcg_set_task_tag(umcg_tid utid, intptr_t tag) - a helper function + used to associate an arbitrary user-provided value + with a umcg task/thread. + + +LIBUMCG API: umcg_get_task_tag() + +intptr_t umcg_get_task_tag(umcg_tid utid) - returns a previously set + task tag, or zero. + + +LIBUMCG API: umcg_create_group() + +umcg_t umcg_create_group(uint32_t flags) - create a UMCG group. + + UMCG servers and workers at LIBUMCG level must belong to the same UMCG + group to interact; note that this is different from UMCG kernel API, + where servers and workers can all interact within the same process. + + UMCG groups are used to partition UMCG tasks (servers and workers) within + a process, e.g. to allow NUMA-aware scheduling. + + +LIBUMCG API: umcg_destroy_group() + +int umcg_destroy_group(umcg_t umcg) - destroy a UMCG group. The group must + be empty, i.e. all its servers and workers must have + unregistered. + + +LIBUMCG API: umcg_register_basic_task() + +umcg_tid umcg_register_basic_task(intptr_t tag) - register the current + thread as a basic LIBUMCG task. + + Basic LIBUMCG tasks do not belong to UMCG groups, and thus cannot + interact with LIBUMCG workers. + + At the kernel level basic LIBUMCG tasks are servers. + + +LIBUMCG API: umcg_register_worker() + +umcg_tid umcg_register_worker(umcg_t group_id, intptr_t tag) - register + the current thread as a LIBUMCG worker in a group. + + LIBUMCG workers, once registered, can forget about being UMCG workers, + as the only difference vs "normal" threads is that now workers are + scheduled not by the kernel, but by servers in their UMCG group, which + happens "transparently" to UMCG workers. + + LIBUMCG workers may call umcg_[wait|wake|swap] to cooperatively share + workload with other LIBUMCG workers in the same group. + + Note: at the moment UMCG workers, once registered, cannnot receive + non-fatal signals. + + +LIBUMCG API: umcg_register_server() + +umcg_tid umcg_register_server(umcg_t group_id, intptr_t tag) - register + the current thread as a LIBUMCG server in a group. + + LIBUMCG servers schedule LIBUMCG workers in the same group via + umcg_get_idle_worker(), umcg_run_worker(), and umcg_preempt_worker(). + See descriptions of these functions below for more details. + + +LIBUMCG API: umcg_unregister_task() + +int umcg_unregister_task(void) - unregister the current thread as a UMCG task. + + A thread can be only one type of a UMCG task at a time. Once unregistered, + a thread can register again as a different UMCG task type, in the same + or a different group. + + +LIBUMCG API: umcg_wait() + +int umcg_wait(uint64_t timeout) - block the current UMCG task until + the timeout expires or it is woken via umcg_wake() or umcg_swap(). + + All UMCG task types can call umcg_wait(). + + +LIBUMCG API: umcg_wake() + +int umcg_wake(umcg_tid next, bool wf_current_cpu) - wake a UMCG task. + + Wake a umcg task if it is blocked as a result of calling umcg_wait() or + umcg_swap(). If @next is NOT blocked in umcg_wait() or umcg_swap(), + it will be marked as "wakeup queued"; when @next calls umcg_wait() or + umcg_swap() later, the "wakeup queued" flag will be removed and + the function will not block. + + Only one wakeup can be queued per task, so calling umcg_wake for + a task with a wakeup queued will spin (in the userspace) until the + wakeup flag is cleared. + + If @next is a worker blocked in umcg_wait(), the worker is added + to the idle workers list so that it will the be picked up by + umcg_get_idle_worker(). + + Note that "wakeup queued" is a purely LIBUMCG (userspace) concept: + the kernel (UMCG kernel API) is unaware of it. + + +LIBUMCG API: umcg_swap() + +int umcg_swap(umcg_tid next, u64 timeout) - block the current task; wake @next. + + umcg_swap() can be used for server-to-server or worker-to-worker + context switches, but NOT server-to-worker or worker-to-server. + If a server wants to context switch with a worker, the server + should call umcg_run_worker(). If a worker wants to context switch + to its server, it should call umcg_wait(). + + In server-to-server context switches, the switching-out server + is RUNNING; the switching-in server can either be IDLE or RUNNING. + If the switching-in server is running, it will have a wakeup queued. + If the switching-out server has a wakeup queued, umcg_swap() will + consume the wakeup. + + In worker-to-worker context switches, the "normal" behavior is that + the RUNNING switching-out worker becomes IDLE, its server is + transferred to the IDLE switching-in worker, and the switching-in + worker becomes RUNNING. + + The switching-in worker MUST NOT be in the idle worker list: it + can either be in umcg_wait(), or pulled out of the idle worker list + previously. + + Same wakeup-queued rules apply to swapping workers as they apply + to swapping servers. + + Note that while with servers umcg_swap() is technically equivalent + to { umcg_wake(); umcg_wait(); }, with possible on-cpu optimizations, + with workers there is a difference, as umcg_swap() will RUN an + idle worker, while umcg_wake() will add it to the idle worker list. + + This difference, however, is transparent for workers: workers + engaging is cooperative scheduling via wait/wake/swap will observe + exactly the same behavior as if they were servers or basic UMCG tasks. + + +LIBUMCG API: umcg_get_idle_worker() + +umcg_tid umcg_get_idle_worker(bool wait) - get an idle worker from + the idle worker list. + + Servers can query for unblocked workers by calling umcg_get_idle_worker(). + + There are two idle worker lists per UMCG group; the kernel-side list, + as described in Documentation/userspace-api/umcg.txt, and the + userspace-side list. umcg_get_idle_worker() first checks the userspace + list and, if it is not empty, returns the first available idle worker, + removing it from the list. + + If the userspace list is empty, the function swaps it with the kernel-side + list of empty workers, and then checks the userspace list again. + + If @wait is true, the function blocks if there are no idle workers + available. The server will be added to the group's idle server list. + The server may also be pointed at by struct umcg_task.idle_server_tid_ptr. + + It is safe to call umcg_get_idle_worker() concurrently. + + +LIBUMCG API: umcg_run_worker() + +umcg_tid umcg_run_worker(umcg_tid worker) - run the worker. + + Servers "run" workers by calling umcg_run_worker(). @worker must be + IDLE, and must NOT be in the idle worker list. I.e. a server may + run a worker that is blocked in umcg_wait() either if umcg_wake() + has NOT been called on the @worker, or if umcg_wake() HAD been + called, and the worker then was returned via umcg_get_idle_worker(). + + umcg_run_worker() will block; if the worker the server is running + swaps with another worker, the server will get reassigned to that + new worker. + + When the worker the server is running blocks, umcg_run_worker returns + the worker's umcg_tid, or UMCG_NONE if the worker unregisters. + + +LIBUMCG API: umcg_preempt_worker() + +int umcg_preempt_worker(umcg_tid worker) - preempt a RUNNING worker. + + The function interrupgs a RUNNING worker and wakes its server. If + the worker is not RUNNING (i.e. BLOCKED or IDLE), the function + returns an error with errno set to EAGAIN. + + The group the worker belongs to must be created with + UMCG_GROUP_ENABLE_PREEMPTION flag set. + + The function may be called from any thread in the process that + @worker belongs to. + + +LIBUMCG API: umcg_get_time_ns() + +uint64_t umcg_get_time_ns(void) - return the current absolute time. + + This function can be used to calculate the absolute timeouts passed + to umcg_wait() and umcg_swap().