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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 84982C433EF for ; Wed, 15 Dec 2021 17:55:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239167AbhLORzL (ORCPT ); Wed, 15 Dec 2021 12:55:11 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43138 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233317AbhLORzL (ORCPT ); Wed, 15 Dec 2021 12:55:11 -0500 Received: from desiato.infradead.org (desiato.infradead.org [IPv6:2001:8b0:10b:1:d65d:64ff:fe57:4e05]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A468CC061574; Wed, 15 Dec 2021 09:55:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=desiato.20200630; h=In-Reply-To:Content-Type:MIME-Version: References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=1F3FEXJ4yhSUpnk3DQ4jfn2zagG0lZEE4SF39YTnx6U=; b=DskP6IKXoJEVDhanbnDjWX84+B MZsZP04WhbVOnigzS8cgl/IeVq1EbAteGjKQq9t+z6nTd5VA3goGkpgWJxaP3igzrtOe63IQyrBTW A4ZU2bvC3JKPnFrS/RzkBVL1kRQq9YU7AYA2VAz3/zc+WyosgoaAdmBaQ+guUgt8dV34csrlsCmrD zKvMrLAKecYP5yvJwkmOXA7F0CDv90yROCla4cS80EMFxZ2CgLcOTjBXVMpiQcMd8BPCph4shIVWf qrcUgwXji8gTuht5Nz948+GcJ3QDmCgo1vhXMkQ1DIjo7k5VMJ8Va/oQF5V5xwv3oSXmIeLIWqM6s u6Fg3Rsw==; Received: from j217100.upc-j.chello.nl ([24.132.217.100] helo=noisy.programming.kicks-ass.net) by desiato.infradead.org with esmtpsa (Exim 4.94.2 #2 (Red Hat Linux)) id 1mxYUI-001XhH-D5; Wed, 15 Dec 2021 17:54:46 +0000 Received: from hirez.programming.kicks-ass.net (hirez.programming.kicks-ass.net [192.168.1.225]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by noisy.programming.kicks-ass.net (Postfix) with ESMTPS id ED208300348; Wed, 15 Dec 2021 18:54:44 +0100 (CET) Received: by hirez.programming.kicks-ass.net (Postfix, from userid 1000) id B10EA20A30BE4; Wed, 15 Dec 2021 18:54:44 +0100 (CET) Date: Wed, 15 Dec 2021 18:54:44 +0100 From: Peter Zijlstra To: Matthew Wilcox 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 , Peter Oskolkov , Andrei Vagin , Jann Horn , Thierry Delisle Subject: Re: [RFC][PATCH 0/3] sched: User Managed Concurrency Groups Message-ID: References: <20211214204445.665580974@infradead.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed, Dec 15, 2021 at 01:49:28PM +0000, Matthew Wilcox wrote: > On Wed, Dec 15, 2021 at 11:44:49AM +0100, Peter Zijlstra wrote: > > On Tue, Dec 14, 2021 at 07:46:25PM -0800, Peter Oskolkov wrote: > > > > > Anyway, I'll test your patchset over the next week or so and let you > > > know if anything really needed is missing (other than waking an idle > > > server if there is one on a worker wakeup; this piece is definitely > > > needed). > > > > Right, so the problem I'm having is that a single idle server ptr like > > before can trivially miss waking annother idle server. > > > > Suppose: > > > > umcg::idle_server_tid_ptr > > > > Then the enqueue_and_wake() thing from the last patch would: > > > > idle_server_tid = xchg((pid_t __user *)self->idle_server_tid_ptr, 0); > > > > to consume the tid, and then use that to enqueue and wake. But what if a > > second wakeup happens right after that? There might be a second idle > > server, but we'll never find it, because userspace hasn't had time to > > update the field again. > > > > Alternatively, we do a linked list of servers, but then every such > > wakeup needs to iterate the whole list, looking for one that has > > UMCG_TF_IDLE set, or something like that, but that lookup is bad for > > performance. > > > > So I'm really not sure what way to go yet. > > 1. Linked lists are fugly and bad for the CPU. Absolutely.. although a stack might work, except for that ABA issue (and contention). > 2. I'm not sure how big the 'N' in 'M:N' is supposed to be. Might be > one per hardware thread? So it could be hundreds-to-thousands, > depending on the scale of system. Typically yes, one server task per hardware thread. Now, I'm also fairly sure you don't want excessive cross-node traffic for this stuff, so that puts a limit on things as well. > 3. The interface between user-kernel could be an array of idle tids, > maybe 16 entries long (16 * 4 = 64 bytes, just one cacheline). As a > server finishes work, it looks for a 0 tid in the batch and stores > its tid in the slot (cmpxchg, I guess, since the array will be shared > between processes). If there are no free slots in the array, then we > definitely have 16 threads already waiting for work, so it can park itself > in whatever data structure userspace wants to use to manage idle servers. > It's up to userspace to decide when to repopulate the array of available > servers from its data structure of idle servers. Right, a tid array might work. Could even have userspace specify the length, then it can do the trade-offs all on it's own. Either a fixed location for each server and a larger array, or clever things, whatever they want. I suppose I'll code up the variable length array, we have space for that.