From mboxrd@z Thu Jan 1 00:00:00 1970 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 14E40C433F5 for ; Wed, 15 Dec 2021 19:50:26 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1670E6B0071; Wed, 15 Dec 2021 14:50:16 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 0EFD86B0072; Wed, 15 Dec 2021 14:50:16 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EAAFD6B0074; Wed, 15 Dec 2021 14:50:15 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0187.hostedemail.com [216.40.44.187]) by kanga.kvack.org (Postfix) with ESMTP id D4AB16B0071 for ; Wed, 15 Dec 2021 14:50:15 -0500 (EST) Received: from smtpin21.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id 80D7B8249980 for ; Wed, 15 Dec 2021 19:50:05 +0000 (UTC) X-FDA: 78921069570.21.5434831 Received: from mail-wr1-f54.google.com (mail-wr1-f54.google.com [209.85.221.54]) by imf11.hostedemail.com (Postfix) with ESMTP id A9AE040004 for ; Wed, 15 Dec 2021 19:50:02 +0000 (UTC) Received: by mail-wr1-f54.google.com with SMTP id t9so40089156wrx.7 for ; Wed, 15 Dec 2021 11:50:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=3JBKbYwsshu8iSqfD9517s+vo2UdPMxMRdjnHJCVbj4=; b=sRpMqDyx/cpoXSV6aAdR8pC8t21f+shsV3RNJFBReQFIZpIbxX8XFW5H67QMW0z346 Lekq/JbkSFs51zuPMhiN0N0FmNxeywvGIGPfhxJDZZofM4xWFPq0IS3+6Rvo7fDqNzxc PGw+mxtOId3D+aoqyi66teuR1yQOjpHnqg93ocrcCQXlft1OJnBtrV45BXQ+6+ubz+D+ sj7ViNnzisl3y2LXbEwh46ph0/9DAQCR2Z+rt2KrrtuhvQi0eAP55ThtvQ4MHEw0TiNG jV/giEUSPIvvfBTzfQQZsGYR5mRR/SmMOiBHkn59tZJB5m/FOku52D7kWqUAl9ZuMy30 bNWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=3JBKbYwsshu8iSqfD9517s+vo2UdPMxMRdjnHJCVbj4=; b=1Hl/GxP+QcWnvpJcSd2gYnoaId8XvzXQBB/sUZq+H5/pbRaMeFD5G91qY8K7HxnEoY dRA9yhGJ7StVt3L5M5CrP6f7PKlxBFV4GwwOKxLmJ95Orag9PQH9+XkuFhLMhlEmcj/A 58QTVmlaCGL4/s4jkcOKxS00fRZd8v3DgaGAg5sZk+CoO1vMnaWeNjSDYry1Mcbvdaz9 Fn0+/OiAYqRSH9TkvvZBxB08bahTshsIW/ytj9rJKVP6qzkagftm1R6POMZ3X5tLCxjQ 9uRSm9lqbek3+39+ZtpiFFjdTsM4QMK+AghjrY6q6KIuQqF9pJA9pSiE7uI56alLvo0v kWLQ== X-Gm-Message-State: AOAM532hiXjj0DQS3DmS/q954QFvsZ6/BmQKQeTlALTnNZgYo+pmBEDU RkvXZMb6HY3vmpe6kVBtUETXqjWd42o87fWiqmEyAA== X-Google-Smtp-Source: ABdhPJzZJskrySYWuhv/jOhIkWrdH0hLSZsgVg63d25D6HdWDBjBSiU7oA1n3Gu5cZ6AIZETV2PYLONoFpL3NUpS76c= X-Received: by 2002:a5d:47ab:: with SMTP id 11mr5996811wrb.148.1639597802997; Wed, 15 Dec 2021 11:50:02 -0800 (PST) MIME-Version: 1.0 References: <20211214204445.665580974@infradead.org> In-Reply-To: From: Peter Oskolkov Date: Wed, 15 Dec 2021 11:49:51 -0800 Message-ID: Subject: Re: [RFC][PATCH 0/3] sched: User Managed Concurrency Groups To: Peter Zijlstra Cc: Peter Oskolkov , Ingo Molnar , Thomas Gleixner , juri.lelli@redhat.com, Vincent Guittot , dietmar.eggemann@arm.com, Steven Rostedt , Ben Segall , mgorman@suse.de, bristot@redhat.com, Linux Kernel Mailing List , Linux Memory Management List , linux-api@vger.kernel.org, x86@kernel.org, Paul Turner , Andrei Vagin , Jann Horn , Thierry Delisle Content-Type: text/plain; charset="UTF-8" X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: A9AE040004 X-Stat-Signature: 1ybc69r9zt9jp6zutp9b8ujtw4x91gtr Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=sRpMqDyx; spf=pass (imf11.hostedemail.com: domain of posk@google.com designates 209.85.221.54 as permitted sender) smtp.mailfrom=posk@google.com; dmarc=pass (policy=reject) header.from=google.com X-HE-Tag: 1639597802-334337 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: On Wed, Dec 15, 2021 at 10:19 AM Peter Zijlstra wrote: > > On Wed, Dec 15, 2021 at 09:56:06AM -0800, Peter Oskolkov wrote: > > > > Right, so the problem I'm having is that a single idle server ptr like > > > before can trivially miss waking annother idle server. > > > > I believe the approach I used in my patchset, suggested by Thierry > > Delisle, works. > > > > In short, there is a single idle server ptr for the kernel to work > > with. The userspace maintains a list of idle servers. If the ptr is > > NULL, the list is empty. When the kernel wakes the idle server it > > sees, the server reaps the runnable worker list and wakes another idle > > server from the userspace list, if available. This newly woken idle > > server repoints the ptr to itself, checks the runnable worker list, to > > avoid missing a woken worker, then goes to sleep. > > > > Why do you think this approach is not OK? > > Suppose at least 4 servers, 2 idle, 2 working. > > Now, the first of the working servers (lets call it S0) gets a wakeup > (say Ta), it finds the idle server (say S3) and consumes it, sticking Ta > on S3 and kicking it alive. TL;DR: our models are different here. In your model a single server can have a bunch of workers interacting with it; in my model only a single RUNNING worker is assigned to a server, which it wakes when it blocks. More details: "Working servers" cannot get wakeups, because a "working server" has a single RUNNING worker attached to it. When a worker blocks, it wakes its attached server and becomes a detached blocked worker (same is true if the worker is "preempted": it blocks and wakes its assigned server). Blocked workers upon wakeup do this, in order: - always add themselves to the runnable worker list (the list is shared among ALL servers, it is NOT per server); - wake a server pointed to by idle_server_ptr, if not NULL; - sleep, waiting for a wakeup from a server; Server S, upon becoming IDLE (no worker to run, or woken on idle server list) does this, in order, in userspace (simplified, see umcg_get_idle_worker() in https://lore.kernel.org/lkml/20211122211327.5931-5-posk@google.com/): - take a userspace (spin) lock (so the steps below are all within a single critical section): - compare_xchg(idle_server_ptr, NULL, S); - if failed, there is another server in idle_server_ptr, so S adds itself to the userspace idle server list, releases the lock, goes to sleep; - if succeeded: - check the runnable worker list; - if empty, release the lock, sleep; - if not empty: - get the list - xchg(idle_server_ptr, NULL) (either S removes itself, or a worker in the kernel does it first, does not matter); - release the lock; - wake server S1 on idle server list. S1 goes through all of these steps. The protocol above serializes the userspace dealing with the idle server ptr/list. Wakeups in the kernel will be caught if there are idle servers. Yes, the protocol in the userspace is complicated (more complicated than outlined above, as the reaped idle/runnable worker list from the kernel is added to the userspace idle/runnable worker list), but the kernel side is very simple. I've tested this interaction extensively, I'm reasonably sure that no worker wakeups are lost. > > Concurrently and loosing the race the other working server (S1) gets a > wake-up from Tb, like said, it lost, no idle server, so Tb goes on the > queue of S1. > > So then S3 wakes, finds Ta and they live happily ever after. > > While S2 and Tb fail to meet one another and both linger in sadness. >