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=-1.1 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_PASS,URIBL_BLOCKED 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 08EBCC4360F for ; Wed, 3 Apr 2019 17:07:03 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id C0E2A2075E for ; Wed, 3 Apr 2019 17:07:02 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="rO2SoqUw" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726387AbfDCRHB (ORCPT ); Wed, 3 Apr 2019 13:07:01 -0400 Received: from userp2130.oracle.com ([156.151.31.86]:36634 "EHLO userp2130.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726099AbfDCRHB (ORCPT ); Wed, 3 Apr 2019 13:07:01 -0400 Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.27/8.16.0.27) with SMTP id x33H3gTb148904; Wed, 3 Apr 2019 17:06:13 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=content-type : mime-version : subject : from : in-reply-to : date : cc : content-transfer-encoding : message-id : references : to; s=corp-2018-07-02; bh=18jsAKrm+I67hogv6dRp6LwocjCgPIU6h3J3TMxV0Fo=; b=rO2SoqUw3cCjVMMU4DE/QsE3rr3wadT1JGVACYIrw26ErfOc9DM7QPddYiwXjscm9Pmk 9T/z/vAwuHuXa36Pjw10aWf/7hlkGDnW4iKFtY2vkDLM5L7CbVDYGcIHNspOUzkWFi7X sUjyJR8ocxzNqXmEgSR+ZBVMu4QQFPRJx6PlAaz5Nb6uuvNvTpQj44btKNjl1tP8L987 N7HveERH0I5yORDJEtmfj+RWbVhgnQjbFhv1wicRDfaLqOHbXEOwYfnTv+4AfrW14o2a j/MBi5fcV7k9CaQP1+v6SfFzbr95bRX9QxI9tuRRHpyQkCfqXQo/rHn2aXvl2Gf0XGqi SA== Received: from userp3030.oracle.com (userp3030.oracle.com [156.151.31.80]) by userp2130.oracle.com with ESMTP id 2rhyvtacuh-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 03 Apr 2019 17:06:12 +0000 Received: from pps.filterd (userp3030.oracle.com [127.0.0.1]) by userp3030.oracle.com (8.16.0.27/8.16.0.27) with SMTP id x33H6CZh009551; Wed, 3 Apr 2019 17:06:12 GMT Received: from userv0122.oracle.com (userv0122.oracle.com [156.151.31.75]) by userp3030.oracle.com with ESMTP id 2rm8f57gws-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 03 Apr 2019 17:06:12 +0000 Received: from abhmp0011.oracle.com (abhmp0011.oracle.com [141.146.116.17]) by userv0122.oracle.com (8.14.4/8.14.4) with ESMTP id x33H5xZr015244; Wed, 3 Apr 2019 17:05:59 GMT Received: from [10.11.111.157] (/10.11.111.157) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Wed, 03 Apr 2019 10:05:59 -0700 Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3259\)) Subject: Re: [PATCH v2 4/5] locking/qspinlock: Introduce starvation avoidance into CNA From: Alex Kogan In-Reply-To: <20190402103750.GN11158@hirez.programming.kicks-ass.net> Date: Wed, 3 Apr 2019 13:06:12 -0400 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 Content-Transfer-Encoding: quoted-printable Message-Id: References: <20190329152006.110370-1-alex.kogan@oracle.com> <20190329152006.110370-5-alex.kogan@oracle.com> <20190402103750.GN11158@hirez.programming.kicks-ass.net> To: Peter Zijlstra X-Mailer: Apple Mail (2.3259) X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=9216 signatures=668685 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1810050000 definitions=main-1904030116 X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=9216 signatures=668685 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1011 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1810050000 definitions=main-1904030116 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org > On Apr 2, 2019, at 6:37 AM, Peter Zijlstra = wrote: >=20 > On Fri, Mar 29, 2019 at 11:20:05AM -0400, Alex Kogan wrote: >> @@ -25,6 +29,18 @@ >>=20 >> #define MCS_NODE(ptr) ((struct mcs_spinlock *)(ptr)) >>=20 >> +/* 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 =3D (node_and_count >> _Q_NODE_OFFSET) - 1; >> @@ -102,6 +118,35 @@ static struct mcs_spinlock = *find_successor(struct mcs_spinlock *me) >> return NULL; >> } >>=20 >> +/* >> + * xorshift function for generating pseudo-random numbers: >> + * = https://urldefense.proofpoint.com/v2/url?u=3Dhttps-3A__en.wikipedia.org_wi= ki_Xorshift&d=3DDwIBAg&c=3DRoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=3D= Hvhk3F4omdCk-GE1PTOm3Kn0A7ApWOZ2aZLTuVxFK4k&m=3DbtYIeJJfSDAM0UloKh-zrG4-Pg= dCMjQMKnvDIqPuEQk&s=3D1UYM9Qd5nozlImYHub0yqRmQCja5hJtnzbHuudtz-nM&e=3D >=20 > Cute; so clearly you've read that page, but then you provide us a > variant that isn't actually listed there. >=20 > 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: >=20 > xorshift32() >=20 > Now, where did you get those parameters from; is this a proper > xorshift32 ? Apologies for the confusion. We are using one of the shift tuples from the Xorshift paper = (https://www.jstatsoft.org/v08/i14/paper), which is referenced by the = wiki page. Those tuples happen to be different from the ones on the wiki page = itself. I do not think we care much, though =E2=80=94 if we keep using xorshift = (see below), we will switch to the variant from the wiki to avoid any = confusion. >=20 > 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. Xorshift seems to be working well enough for our purposes, while those = other variants are slightly more expensive and have a larger state. >=20 >> + >> +/* >> + * Return false with probability 1 / @range. >> + * @range must be a power of 2. >> + */ >> +static bool probably(unsigned int range) >> +{ >> + return xor_random() & (range - 1); >> +} >=20 > 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? probably() would return 0 if and only if xor_random() returns 0 in the = lowest log_2(range) bits, which should happen with probability of 1/(2^log_2(range))=3D1/range. >=20 > 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. We will check the impact of using next_pseudo_random32(). > Also, we actually have xorshift32 already in tree in > lib/test_hash.c. I see that now. We can certainly use this function instead.=20 If we end up doing that, any suggestion where it should be moved to be = called from multiple places (the original lib/test_hash.c and our CNA = code)? Thanks, =E2=80=94 Alex= From mboxrd@z Thu Jan 1 00:00:00 1970 From: Alex Kogan Subject: Re: [PATCH v2 4/5] locking/qspinlock: Introduce starvation avoidance into CNA Date: Wed, 3 Apr 2019 13:06:12 -0400 Message-ID: References: <20190329152006.110370-1-alex.kogan@oracle.com> <20190329152006.110370-5-alex.kogan@oracle.com> <20190402103750.GN11158@hirez.programming.kicks-ass.net> Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3259\)) Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: In-Reply-To: <20190402103750.GN11158@hirez.programming.kicks-ass.net> 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: Peter Zijlstra 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 Cj4gT24gQXByIDIsIDIwMTksIGF0IDY6MzcgQU0sIFBldGVyIFppamxzdHJhIDxwZXRlcnpAaW5m cmFkZWFkLm9yZz4gd3JvdGU6Cj4gCj4gT24gRnJpLCBNYXIgMjksIDIwMTkgYXQgMTE6MjA6MDVB TSAtMDQwMCwgQWxleCBLb2dhbiB3cm90ZToKPj4gQEAgLTI1LDYgKzI5LDE4IEBACj4+IAo+PiAj ZGVmaW5lIE1DU19OT0RFKHB0cikgKChzdHJ1Y3QgbWNzX3NwaW5sb2NrICopKHB0cikpCj4+IAo+ PiArLyogUGVyLUNQVSBwc2V1ZG8tcmFuZG9tIG51bWJlciBzZWVkICovCj4+ICtzdGF0aWMgREVG SU5FX1BFUl9DUFUodTMyLCBzZWVkKTsKPj4gKwo+PiArLyoKPj4gKyAqIENvbnRyb2xzIHRoZSBw cm9iYWJpbGl0eSBmb3IgaW50cmEtbm9kZSBsb2NrIGhhbmQtb2ZmLiBJdCBjYW4gYmUKPj4gKyAq IHR1bmVkIGFuZCBkZXBlbmQsIGUuZy4sIG9uIHRoZSBudW1iZXIgb2YgQ1BVcyBwZXIgbm9kZS4g Rm9yIG5vdywKPj4gKyAqIGNob29zZSBhIHZhbHVlIHRoYXQgcHJvdmlkZXMgcmVhc29uYWJsZSBs b25nLXRlcm0gZmFpcm5lc3Mgd2l0aG91dAo+PiArICogc2FjcmlmaWNpbmcgcGVyZm9ybWFuY2Ug Y29tcGFyZWQgdG8gYSB2ZXJzaW9uIHRoYXQgZG9lcyBub3QgaGF2ZSBhbnkKPj4gKyAqIGZhaXJu ZXNzIGd1YXJhbnRlZXMuCj4+ICsgKi8KPj4gKyNkZWZpbmUgSU5UUkFfTk9ERV9IQU5ET0ZGX1BS T0JfQVJHIDB4MTAwMDAKPj4gKwo+PiBzdGF0aWMgaW5saW5lIF9fcHVyZSBpbnQgZGVjb2RlX251 bWFfbm9kZSh1MzIgbm9kZV9hbmRfY291bnQpCj4+IHsKPj4gCWludCBub2RlID0gKG5vZGVfYW5k X2NvdW50ID4+IF9RX05PREVfT0ZGU0VUKSAtIDE7Cj4+IEBAIC0xMDIsNiArMTE4LDM1IEBAIHN0 YXRpYyBzdHJ1Y3QgbWNzX3NwaW5sb2NrICpmaW5kX3N1Y2Nlc3NvcihzdHJ1Y3QgbWNzX3NwaW5s b2NrICptZSkKPj4gCXJldHVybiBOVUxMOwo+PiB9Cj4+IAo+PiArLyoKPj4gKyAqIHhvcnNoaWZ0 IGZ1bmN0aW9uIGZvciBnZW5lcmF0aW5nIHBzZXVkby1yYW5kb20gbnVtYmVyczoKPj4gKyAqIGh0 dHBzOi8vdXJsZGVmZW5zZS5wcm9vZnBvaW50LmNvbS92Mi91cmw/dT1odHRwcy0zQV9fZW4ud2lr aXBlZGlhLm9yZ193aWtpX1hvcnNoaWZ0JmQ9RHdJQkFnJmM9Um9QMVl1bUNYQ2dhV0h2bFpZUjhQ Wmg4QnY3cUlyTVVCNjVlYXBJX0puRSZyPUh2aGszRjRvbWRDay1HRTFQVE9tM0tuMEE3QXBXT1oy YVpMVHVWeEZLNGsmbT1idFlJZUpKZlNEQU0wVWxvS2gtenJHNC1QZ2RDTWpRTUtudkRJcVB1RVFr JnM9MVVZTTlRZDVub3psSW1ZSHViMHlxUm1RQ2phNWhKdG56Ykh1dWR0ei1uTSZlPQo+IAo+IEN1 dGU7IHNvIGNsZWFybHkgeW91J3ZlIHJlYWQgdGhhdCBwYWdlLCBidXQgdGhlbiB5b3UgcHJvdmlk ZSB1cyBhCj4gdmFyaWFudCB0aGF0IGlzbid0IGFjdHVhbGx5IGxpc3RlZCB0aGVyZS4KPiAKPiBZ b3VyIG5hbWluZyBpcyBhbHNvIG5vbi1zdGFuZGFyZCBpbiB0aGF0IGl0IGRvZXMgbm90IHJlbGF5 IHRoZSBwZXJpb2QuCj4gVGhlIHR5cGUgc2VlbXMgdG8gc3VnZ2VzdCAzMmJpdCwgc28gdGhlIG5h bWUgc2hvdWxkIHRoZW4gaGF2ZSBiZWVuOgo+IAo+ICB4b3JzaGlmdDMyKCkKPiAKPiBOb3csIHdo ZXJlIGRpZCB5b3UgZ2V0IHRob3NlIHBhcmFtZXRlcnMgZnJvbTsgaXMgdGhpcyBhIHByb3Blcgo+ IHhvcnNoaWZ0MzIgPwpBcG9sb2dpZXMgZm9yIHRoZSBjb25mdXNpb24uCldlIGFyZSB1c2luZyBv bmUgb2YgdGhlIHNoaWZ0IHR1cGxlcyBmcm9tIHRoZSBYb3JzaGlmdCBwYXBlciAoaHR0cHM6Ly93 d3cuanN0YXRzb2Z0Lm9yZy92MDgvaTE0L3BhcGVyKSwgd2hpY2ggaXMgcmVmZXJlbmNlZCBieSB0 aGUgd2lraSBwYWdlLgpUaG9zZSB0dXBsZXMgaGFwcGVuIHRvIGJlIGRpZmZlcmVudCBmcm9tIHRo ZSBvbmVzIG9uIHRoZSB3aWtpIHBhZ2UgaXRzZWxmLgpJIGRvIG5vdCB0aGluayB3ZSBjYXJlIG11 Y2gsIHRob3VnaCDigJQgaWYgd2Uga2VlcCB1c2luZyB4b3JzaGlmdCAoc2VlIGJlbG93KSwgd2Ug d2lsbCBzd2l0Y2ggdG8gdGhlIHZhcmlhbnQgZnJvbSB0aGUgd2lraSB0byBhdm9pZCBhbnkgY29u ZnVzaW9uLgoKPiAKPiBOb3csIHlvdSd2ZSByZWFkIHRoYXQgcGFnZSBhbmQgeW91IGtub3cgdGhl cmUncyAndHJpdmlhbCcgaW1wcm92ZW1lbnRzCj4gb24gdGhlIHB1cmUgeG9yc2hpZnQsIHdoeSBu b3QgcGljayBvbmUgb2YgdGhvc2U/IHhvcndvdyBzZWVtcyBjaGVhcAo+IGVub3VnaCwgb3IgdGhh dCB4b3JzaGlmdDEyOHBsdXMoKSBvbmUuClhvcnNoaWZ0IHNlZW1zIHRvIGJlIHdvcmtpbmcgd2Vs bCBlbm91Z2ggZm9yIG91ciBwdXJwb3Nlcywgd2hpbGUgdGhvc2Ugb3RoZXIgdmFyaWFudHMgYXJl IHNsaWdodGx5IG1vcmUgZXhwZW5zaXZlIGFuZCBoYXZlIGEgbGFyZ2VyIHN0YXRlLgoKPiAKPj4g Kwo+PiArLyoKPj4gKyAqIFJldHVybiBmYWxzZSB3aXRoIHByb2JhYmlsaXR5IDEgLyBAcmFuZ2Uu Cj4+ICsgKiBAcmFuZ2UgbXVzdCBiZSBhIHBvd2VyIG9mIDIuCj4+ICsgKi8KPj4gK3N0YXRpYyBi b29sIHByb2JhYmx5KHVuc2lnbmVkIGludCByYW5nZSkKPj4gK3sKPj4gKwlyZXR1cm4geG9yX3Jh bmRvbSgpICYgKHJhbmdlIC0gMSk7Cj4+ICt9Cj4gCj4gVWhoLCB5b3Ugc3VyZSB0aGF0J3Mgd2hh dCBpdCBkb2VzPyBUaGUgb25seSB3YXkgZm9yIHRoYXQgdG8gcmV0dXJuIGZhbHNlCj4gaXMgd2hl biBhbGwgQHJhbmdlIGJpdHMgYXJlIDAsIHdoaWNoIGhhcHBlbnMgb25jZSAoMl4zMi9yYW5nZSkt MSB0aW1lcywKPiBvciBhbSBJIG1pc3Rha2VuPwoKcHJvYmFibHkoKSB3b3VsZCByZXR1cm4gMCBp ZiBhbmQgb25seSBpZiB4b3JfcmFuZG9tKCkgcmV0dXJucyAwIGluIHRoZSBsb3dlc3QgbG9nXzIo cmFuZ2UpIGJpdHMsCndoaWNoIHNob3VsZCBoYXBwZW4gd2l0aCBwcm9iYWJpbGl0eSBvZiAxLygy XmxvZ18yKHJhbmdlKSk9MS9yYW5nZS4KCj4gCj4gQWxzbywgbGludXgvcmFuZG9tLmggaW5jbHVk ZXMgbmV4dF9wc2V1ZG9fcmFuZG9tMzIoKSwgc2hvdWxkIHdlIGJlIHVzaW5nCj4gdGhhdD8gQXJn dWFibHkgdGhhdCdzIG1vcmUgZXhwZW5zaXZlIG9uIGEgbnVtYmVyIG9mIHBsYXRmb3JtcyBkdWUg dG8gdGhlCj4gbXVsdGlwbGljYXRpb24uCldlIHdpbGwgY2hlY2sgdGhlIGltcGFjdCBvZiB1c2lu ZyBuZXh0X3BzZXVkb19yYW5kb20zMigpLgoKPiBBbHNvLCB3ZSBhY3R1YWxseSBoYXZlIHhvcnNo aWZ0MzIgYWxyZWFkeSBpbiB0cmVlIGluCj4gbGliL3Rlc3RfaGFzaC5jLgpJIHNlZSB0aGF0IG5v dy4gV2UgY2FuIGNlcnRhaW5seSB1c2UgdGhpcyBmdW5jdGlvbiBpbnN0ZWFkLiAKSWYgd2UgZW5k IHVwIGRvaW5nIHRoYXQsIGFueSBzdWdnZXN0aW9uIHdoZXJlIGl0IHNob3VsZCBiZSBtb3ZlZCB0 byBiZSBjYWxsZWQgZnJvbSBtdWx0aXBsZSBwbGFjZXMgKHRoZSBvcmlnaW5hbCBsaWIvdGVzdF9o YXNoLmMgYW5kIG91ciBDTkEgY29kZSk/CgpUaGFua3MsCuKAlCBBbGV4Cl9fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fCmxpbnV4LWFybS1rZXJuZWwgbWFpbGlu ZyBsaXN0CmxpbnV4LWFybS1rZXJuZWxAbGlzdHMuaW5mcmFkZWFkLm9yZwpodHRwOi8vbGlzdHMu aW5mcmFkZWFkLm9yZy9tYWlsbWFuL2xpc3RpbmZvL2xpbnV4LWFybS1rZXJuZWwK