From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Zijlstra Subject: Re: [PATCH v2 4/5] locking/qspinlock: Introduce starvation avoidance into CNA Date: Tue, 2 Apr 2019 12:37:50 +0200 Message-ID: <20190402103750.GN11158@hirez.programming.kicks-ass.net> References: <20190329152006.110370-1-alex.kogan@oracle.com> <20190329152006.110370-5-alex.kogan@oracle.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: Content-Disposition: inline In-Reply-To: <20190329152006.110370-5-alex.kogan@oracle.com> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=m.gmane.org@lists.infradead.org To: Alex Kogan Cc: linux-arch@vger.kernel.org, tytso@mit.edu, arnd@arndb.de, dave.dice@oracle.com, x86@kernel.org, will.deacon@arm.com, linux@armlinux.org.uk, steven.sistare@oracle.com, linux-kernel@vger.kernel.org, rahul.x.yadav@oracle.com, mingo@redhat.com, bp@alien8.de, hpa@zytor.com, longman@redhat.com, tglx@linutronix.de, daniel.m.jordan@oracle.com, linux-arm-kernel@lists.infradead.org List-Id: linux-arch.vger.kernel.org On Fri, Mar 29, 2019 at 11:20:05AM -0400, Alex Kogan wrote: > @@ -25,6 +29,18 @@ > > #define MCS_NODE(ptr) ((struct mcs_spinlock *)(ptr)) > > +/* Per-CPU pseudo-random number seed */ > +static DEFINE_PER_CPU(u32, seed); > + > +/* > + * Controls the probability for intra-node lock hand-off. It can be > + * tuned and depend, e.g., on the number of CPUs per node. For now, > + * choose a value that provides reasonable long-term fairness without > + * sacrificing performance compared to a version that does not have any > + * fairness guarantees. > + */ > +#define INTRA_NODE_HANDOFF_PROB_ARG 0x10000 > + > static inline __pure int decode_numa_node(u32 node_and_count) > { > int node = (node_and_count >> _Q_NODE_OFFSET) - 1; > @@ -102,6 +118,35 @@ static struct mcs_spinlock *find_successor(struct mcs_spinlock *me) > return NULL; > } > > +/* > + * xorshift function for generating pseudo-random numbers: > + * https://en.wikipedia.org/wiki/Xorshift Cute; so clearly you've read that page, but then you provide us a variant that isn't actually listed there. Your naming is also non-standard in that it does not relay the period. The type seems to suggest 32bit, so the name should then have been: xorshift32() Now, where did you get those parameters from; is this a proper xorshift32 ? > + */ > +static inline u32 xor_random(void) > +{ > + u32 v; > + > + v = this_cpu_read(seed); > + if (v == 0) > + get_random_bytes(&v, sizeof(u32)); Given xorshift is a LFSR subset, the above case will only ever happen _once_ and it seems like bad form to stick it here instead of in a init function. Also, does it really matter, can't we simply initialize the variable with a !0 value and call it a day? As to that variable, seed is clearly a misnomer, the wiki page you reference calls it state, which might be a little ambiguous, xs_state otoh should work just fine. > + v ^= v << 6; > + v ^= v >> 21; > + v ^= v << 7; > + this_cpu_write(seed, v); > + > + return v; > +} Now, you've read that page and you know there's 'trivial' improvements on the pure xorshift, why not pick one of those? xorwow seems cheap enough, or that xorshift128plus() one. > + > +/* > + * Return false with probability 1 / @range. > + * @range must be a power of 2. > + */ > +static bool probably(unsigned int range) > +{ > + return xor_random() & (range - 1); > +} Uhh, you sure that's what it does? The only way for that to return false is when all @range bits are 0, which happens once (2^32/range)-1 times, or am I mistaken? Also, linux/random.h includes next_pseudo_random32(), should we be using that? Arguably that's more expensive on a number of platforms due to the multiplication. Also, we actually have xorshift32 already in tree in lib/test_hash.c. The advantage of next_psuedo_random32() is that it doesn't have that 0 identify that pure LFSRs suffer from and it has 0 state. Now at a glance, the xorwow/xorshift128plus variants don't seem to suffer that 0 identify, so that's good, but they still have fairly large state. It also seems unfortunate to litter the tree with custom PRNGs. Ted? From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from bombadil.infradead.org ([198.137.202.133]:37464 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726193AbfDBKiE (ORCPT ); Tue, 2 Apr 2019 06:38:04 -0400 Date: Tue, 2 Apr 2019 12:37:50 +0200 From: Peter Zijlstra Subject: Re: [PATCH v2 4/5] locking/qspinlock: Introduce starvation avoidance into CNA Message-ID: <20190402103750.GN11158@hirez.programming.kicks-ass.net> References: <20190329152006.110370-1-alex.kogan@oracle.com> <20190329152006.110370-5-alex.kogan@oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20190329152006.110370-5-alex.kogan@oracle.com> Sender: linux-arch-owner@vger.kernel.org List-ID: To: Alex Kogan Cc: linux@armlinux.org.uk, mingo@redhat.com, will.deacon@arm.com, arnd@arndb.de, longman@redhat.com, linux-arch@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-kernel@vger.kernel.org, tglx@linutronix.de, bp@alien8.de, hpa@zytor.com, x86@kernel.org, steven.sistare@oracle.com, daniel.m.jordan@oracle.com, dave.dice@oracle.com, rahul.x.yadav@oracle.com, tytso@mit.edu Message-ID: <20190402103750.ZtrGaMGKsS5Z7zIcibJnU7HXa-znVOhiez9sPw0TkSk@z> On Fri, Mar 29, 2019 at 11:20:05AM -0400, Alex Kogan wrote: > @@ -25,6 +29,18 @@ > > #define MCS_NODE(ptr) ((struct mcs_spinlock *)(ptr)) > > +/* Per-CPU pseudo-random number seed */ > +static DEFINE_PER_CPU(u32, seed); > + > +/* > + * Controls the probability for intra-node lock hand-off. It can be > + * tuned and depend, e.g., on the number of CPUs per node. For now, > + * choose a value that provides reasonable long-term fairness without > + * sacrificing performance compared to a version that does not have any > + * fairness guarantees. > + */ > +#define INTRA_NODE_HANDOFF_PROB_ARG 0x10000 > + > static inline __pure int decode_numa_node(u32 node_and_count) > { > int node = (node_and_count >> _Q_NODE_OFFSET) - 1; > @@ -102,6 +118,35 @@ static struct mcs_spinlock *find_successor(struct mcs_spinlock *me) > return NULL; > } > > +/* > + * xorshift function for generating pseudo-random numbers: > + * https://en.wikipedia.org/wiki/Xorshift Cute; so clearly you've read that page, but then you provide us a variant that isn't actually listed there. Your naming is also non-standard in that it does not relay the period. The type seems to suggest 32bit, so the name should then have been: xorshift32() Now, where did you get those parameters from; is this a proper xorshift32 ? > + */ > +static inline u32 xor_random(void) > +{ > + u32 v; > + > + v = this_cpu_read(seed); > + if (v == 0) > + get_random_bytes(&v, sizeof(u32)); Given xorshift is a LFSR subset, the above case will only ever happen _once_ and it seems like bad form to stick it here instead of in a init function. Also, does it really matter, can't we simply initialize the variable with a !0 value and call it a day? As to that variable, seed is clearly a misnomer, the wiki page you reference calls it state, which might be a little ambiguous, xs_state otoh should work just fine. > + v ^= v << 6; > + v ^= v >> 21; > + v ^= v << 7; > + this_cpu_write(seed, v); > + > + return v; > +} Now, you've read that page and you know there's 'trivial' improvements on the pure xorshift, why not pick one of those? xorwow seems cheap enough, or that xorshift128plus() one. > + > +/* > + * Return false with probability 1 / @range. > + * @range must be a power of 2. > + */ > +static bool probably(unsigned int range) > +{ > + return xor_random() & (range - 1); > +} Uhh, you sure that's what it does? The only way for that to return false is when all @range bits are 0, which happens once (2^32/range)-1 times, or am I mistaken? Also, linux/random.h includes next_pseudo_random32(), should we be using that? Arguably that's more expensive on a number of platforms due to the multiplication. Also, we actually have xorshift32 already in tree in lib/test_hash.c. The advantage of next_psuedo_random32() is that it doesn't have that 0 identify that pure LFSRs suffer from and it has 0 state. Now at a glance, the xorwow/xorshift128plus variants don't seem to suffer that 0 identify, so that's good, but they still have fairly large state. It also seems unfortunate to litter the tree with custom PRNGs. Ted? 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 X-Spam-Level: X-Spam-Status: No, score=-2.5 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_PASS, URIBL_BLOCKED,USER_AGENT_MUTT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A376EC4360F for ; Tue, 2 Apr 2019 10:38:03 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 6E7AE2084C for ; Tue, 2 Apr 2019 10:38:03 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="uesRe5WO" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 6E7AE2084C Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=infradead.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:Cc:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References: Message-ID:Subject:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=v0iS56WVdh4LX3AH5/mU1JTqd2V9OD1NgRWpSOqN6Ys=; b=uesRe5WOjxFxYG rXJ5lNYJxDvm5bfstC0SSYO6LNO2r2wcK0mld2E7G0qSrIjEKFF5ZDMCdKWwyjrHArO71jMQ8M376 GdO4/o3LxZ29llE6lmv5r8uhwxhcw3QEijrgM5jsWpHkQIWUDGZvS9UVz6FfQvSfBWhQm/4yDQHXU Ated6iXzj6RNHlzbCTwNilwYI8gkOZbEtI03Y18QhIcCm5FuVKrm1i78iNVSteMOduFIJkYQ5wEqs fPPDrZh6sbEv3SPAakMYO517dmrei033YJ49InR61B90rEch2LJ6HIrj3NUoMcfJuxp4K5X6oU6b3 a+zLCixXJbIIWVFIAmIA==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.90_1 #2 (Red Hat Linux)) id 1hBGnj-0004Dz-S1; Tue, 02 Apr 2019 10:37:55 +0000 Received: from j217100.upc-j.chello.nl ([24.132.217.100] helo=hirez.programming.kicks-ass.net) by bombadil.infradead.org with esmtpsa (Exim 4.90_1 #2 (Red Hat Linux)) id 1hBGng-0004Dc-Qi; Tue, 02 Apr 2019 10:37:52 +0000 Received: by hirez.programming.kicks-ass.net (Postfix, from userid 1000) id E00BB203CBE11; Tue, 2 Apr 2019 12:37:50 +0200 (CEST) Date: Tue, 2 Apr 2019 12:37:50 +0200 From: Peter Zijlstra To: Alex Kogan Subject: Re: [PATCH v2 4/5] locking/qspinlock: Introduce starvation avoidance into CNA Message-ID: <20190402103750.GN11158@hirez.programming.kicks-ass.net> References: <20190329152006.110370-1-alex.kogan@oracle.com> <20190329152006.110370-5-alex.kogan@oracle.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20190329152006.110370-5-alex.kogan@oracle.com> User-Agent: Mutt/1.10.1 (2018-07-13) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: linux-arch@vger.kernel.org, tytso@mit.edu, arnd@arndb.de, dave.dice@oracle.com, x86@kernel.org, will.deacon@arm.com, linux@armlinux.org.uk, steven.sistare@oracle.com, linux-kernel@vger.kernel.org, rahul.x.yadav@oracle.com, mingo@redhat.com, bp@alien8.de, hpa@zytor.com, longman@redhat.com, tglx@linutronix.de, daniel.m.jordan@oracle.com, linux-arm-kernel@lists.infradead.org Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Fri, Mar 29, 2019 at 11:20:05AM -0400, Alex Kogan wrote: > @@ -25,6 +29,18 @@ > > #define MCS_NODE(ptr) ((struct mcs_spinlock *)(ptr)) > > +/* Per-CPU pseudo-random number seed */ > +static DEFINE_PER_CPU(u32, seed); > + > +/* > + * Controls the probability for intra-node lock hand-off. It can be > + * tuned and depend, e.g., on the number of CPUs per node. For now, > + * choose a value that provides reasonable long-term fairness without > + * sacrificing performance compared to a version that does not have any > + * fairness guarantees. > + */ > +#define INTRA_NODE_HANDOFF_PROB_ARG 0x10000 > + > static inline __pure int decode_numa_node(u32 node_and_count) > { > int node = (node_and_count >> _Q_NODE_OFFSET) - 1; > @@ -102,6 +118,35 @@ static struct mcs_spinlock *find_successor(struct mcs_spinlock *me) > return NULL; > } > > +/* > + * xorshift function for generating pseudo-random numbers: > + * https://en.wikipedia.org/wiki/Xorshift Cute; so clearly you've read that page, but then you provide us a variant that isn't actually listed there. Your naming is also non-standard in that it does not relay the period. The type seems to suggest 32bit, so the name should then have been: xorshift32() Now, where did you get those parameters from; is this a proper xorshift32 ? > + */ > +static inline u32 xor_random(void) > +{ > + u32 v; > + > + v = this_cpu_read(seed); > + if (v == 0) > + get_random_bytes(&v, sizeof(u32)); Given xorshift is a LFSR subset, the above case will only ever happen _once_ and it seems like bad form to stick it here instead of in a init function. Also, does it really matter, can't we simply initialize the variable with a !0 value and call it a day? As to that variable, seed is clearly a misnomer, the wiki page you reference calls it state, which might be a little ambiguous, xs_state otoh should work just fine. > + v ^= v << 6; > + v ^= v >> 21; > + v ^= v << 7; > + this_cpu_write(seed, v); > + > + return v; > +} Now, you've read that page and you know there's 'trivial' improvements on the pure xorshift, why not pick one of those? xorwow seems cheap enough, or that xorshift128plus() one. > + > +/* > + * Return false with probability 1 / @range. > + * @range must be a power of 2. > + */ > +static bool probably(unsigned int range) > +{ > + return xor_random() & (range - 1); > +} Uhh, you sure that's what it does? The only way for that to return false is when all @range bits are 0, which happens once (2^32/range)-1 times, or am I mistaken? Also, linux/random.h includes next_pseudo_random32(), should we be using that? Arguably that's more expensive on a number of platforms due to the multiplication. Also, we actually have xorshift32 already in tree in lib/test_hash.c. The advantage of next_psuedo_random32() is that it doesn't have that 0 identify that pure LFSRs suffer from and it has 0 state. Now at a glance, the xorwow/xorshift128plus variants don't seem to suffer that 0 identify, so that's good, but they still have fairly large state. It also seems unfortunate to litter the tree with custom PRNGs. Ted? _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel