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=-15.8 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=unavailable 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 7B28DC433B4 for ; Wed, 14 Apr 2021 18:19:46 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 427B161177 for ; Wed, 14 Apr 2021 18:19:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1353261AbhDNSUD (ORCPT ); Wed, 14 Apr 2021 14:20:03 -0400 Received: from userp2130.oracle.com ([156.151.31.86]:57138 "EHLO userp2130.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1353073AbhDNSTi (ORCPT ); Wed, 14 Apr 2021 14:19:38 -0400 Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 13EI3qhc126356; Wed, 14 Apr 2021 18:18:21 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-2020-01-29; bh=gLGuc0MbwC1hbqSzhPV007H4I1ORU4K5O+TznHWynCk=; b=PQVoeIpjkonbJIa8tkqqaN5uVs9M4jOu/Jmuk93yrCMBZQT6K2/OgDsxINiUwIVfonGf 5O4BI7+J18NE9jnx+gXsDhEvKP4SHoomiTdVqi/WFNnBQ2Ybk+sFHixT17eLhizOcgwp o0yh0//sR0+gYNyh0OpW8odEtHo/6+JIsZ2y7698Mm35lwr8HG1LERmlfh+XY1HCSsIF 1NgM5fGU05YoIqLEGgSsdUhyWr5npwdQ4cHpB9z2WGyNzLF19B4rmx911/NrhRWNyvSl fGcQEWgVZ4LosmlqKRAQsXXgk14b+VePDT6/rCC7sBA/3H0CGWKNN7Mqpano5akGM9Yx Gw== Received: from aserp3020.oracle.com (aserp3020.oracle.com [141.146.126.70]) by userp2130.oracle.com with ESMTP id 37u3erke32-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Apr 2021 18:18:21 +0000 Received: from pps.filterd (aserp3020.oracle.com [127.0.0.1]) by aserp3020.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 13EI5k3Y125745; Wed, 14 Apr 2021 18:18:17 GMT Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by aserp3020.oracle.com with ESMTP id 37unx1q3fu-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Apr 2021 18:18:17 +0000 Received: from abhmp0007.oracle.com (abhmp0007.oracle.com [141.146.116.13]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id 13EII8L6015694; Wed, 14 Apr 2021 18:18:08 GMT Received: from [10.39.249.3] (/10.39.249.3) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Wed, 14 Apr 2021 11:18:07 -0700 Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\)) Subject: Re: [External] : Re: [PATCH v14 6/6] locking/qspinlock: Introduce the shuffle reduction optimization into CNA From: Alex Kogan In-Reply-To: Date: Wed, 14 Apr 2021 14:18:05 -0400 Cc: linux@armlinux.org.uk, Peter Zijlstra , Ingo Molnar , Will Deacon , 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, guohanjun@huawei.com, jglauber@marvell.com, steven.sistare@oracle.com, daniel.m.jordan@oracle.com, dave.dice@oracle.com Content-Transfer-Encoding: quoted-printable Message-Id: <96EB342A-1343-4D71-B687-6EED27159161@oracle.com> References: <20210401153156.1165900-1-alex.kogan@oracle.com> <20210401153156.1165900-7-alex.kogan@oracle.com> To: Andreas Herrmann X-Mailer: Apple Mail (2.3608.120.23.2.4) X-Proofpoint-IMR: 1 X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=9954 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 suspectscore=0 mlxscore=0 malwarescore=0 adultscore=0 bulkscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104060000 definitions=main-2104140118 X-Proofpoint-ORIG-GUID: 39TCaFnEN6owMAOcL_9f8xo3oSQ__Tm0 X-Proofpoint-GUID: 39TCaFnEN6owMAOcL_9f8xo3oSQ__Tm0 X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=9954 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 priorityscore=1501 clxscore=1011 adultscore=0 mlxlogscore=999 bulkscore=0 malwarescore=0 spamscore=0 impostorscore=0 suspectscore=0 mlxscore=0 phishscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104060000 definitions=main-2104140118 Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi, Andreas. Thanks for the great questions. > On Apr 14, 2021, at 3:47 AM, Andreas Herrmann = wrote: >=20 > On Thu, Apr 01, 2021 at 11:31:56AM -0400, Alex Kogan wrote: >> This performance optimization chooses probabilistically to avoid = moving >> threads from the main queue into the secondary one when the secondary = queue >> is empty. >>=20 >> It is helpful when the lock is only lightly contended. In particular, = it >> makes CNA less eager to create a secondary queue, but does not = introduce >> any extra delays for threads waiting in that queue once it is = created. >>=20 >> Signed-off-by: Alex Kogan >> Reviewed-by: Steve Sistare >> Reviewed-by: Waiman Long >> --- >> kernel/locking/qspinlock_cna.h | 39 = ++++++++++++++++++++++++++++++++++ >> 1 file changed, 39 insertions(+) >>=20 >> diff --git a/kernel/locking/qspinlock_cna.h = b/kernel/locking/qspinlock_cna.h >> index 29c3abbd3d94..983c6a47a221 100644 >> --- a/kernel/locking/qspinlock_cna.h >> +++ b/kernel/locking/qspinlock_cna.h >> @@ -5,6 +5,7 @@ >>=20 >> #include >> #include >> +#include >>=20 >> /* >> * Implement a NUMA-aware version of MCS (aka CNA, or compact = NUMA-aware lock). >> @@ -86,6 +87,34 @@ static inline bool = intra_node_threshold_reached(struct cna_node *cn) >> return current_time - threshold > 0; >> } >>=20 >> +/* >> + * Controls the probability for enabling the ordering of the main = queue >> + * when the secondary queue is empty. The chosen value reduces the = amount >> + * of unnecessary shuffling of threads between the two waiting = queues >> + * when the contention is low, while responding fast enough and = enabling >> + * the shuffling when the contention is high. >> + */ >> +#define SHUFFLE_REDUCTION_PROB_ARG (7) >=20 > Out of curiosity: >=20 > Have you used other values and done measurements what's an efficient > value for SHUFFLE_REDUCTION_PROB_ARG? Yes, we did try other values. Small variations do not change the results = much, but if you bump the value significantly (e.g., 20), you end up with a = lock that hardly does any shuffling and thus performs on-par with the (MCS-based) baseline. > Maybe I miscalculated it, but if I understand it correctly this value > implies that the propability is 0.9921875 that below function returns > true. Your analysis is correct. Intuitively, we tried to keep the probability = around 1-2%, so if we do decide to shuffle when we don=E2=80=99t really want to = (i.e., when the contention is low), the overall overhead of such wrong decisions would = be small. >=20 > My question is probably answered by following statement from > referenced paper: >=20 > "In our experiments with the shuffle reduction optimization enabled, > we set THRESHOLD2 to 0xff." (page with figure 5) Yeah, just to avoid any confusion =E2=80=94 we used a different = mechanism to draw pseudo-random numbers in the paper, so that 0xff number is not directly=20= comparable to the range of possible values for = SHUFFLE_REDUCTION_PROB_ARG, but the idea was exactly the same. >=20 >> + >> +/* Per-CPU pseudo-random number seed */ >> +static DEFINE_PER_CPU(u32, seed); >> + >> +/* >> + * Return false with probability 1 / 2^@num_bits. >> + * Intuitively, the larger @num_bits the less likely false is to be = returned. >> + * @num_bits must be a number between 0 and 31. >> + */ >> +static bool probably(unsigned int num_bits) >> +{ >> + u32 s; >> + >> + s =3D this_cpu_read(seed); >> + s =3D next_pseudo_random32(s); >> + this_cpu_write(seed, s); >> + >> + return s & ((1 << num_bits) - 1); >> +} >> + >> static void __init cna_init_nodes_per_cpu(unsigned int cpu) >> { >> struct mcs_spinlock *base =3D per_cpu_ptr(&qnodes[0].mcs, cpu); >> @@ -293,6 +322,16 @@ static __always_inline u32 = cna_wait_head_or_lock(struct qspinlock *lock, >> { >> struct cna_node *cn =3D (struct cna_node *)node; >>=20 >> + if (node->locked <=3D 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) = { >=20 > Again if I understand it correctly with SHUFFLE_REDUCTION_PROB_ARG=3D=3D= 7 > it's roughly 1 out of 100 cases where probably() returns false. >=20 > Why/when is this beneficial? >=20 > I assume it has to do with following statement in the referenced > paper: >=20 > "The superior performance over MCS at 4 threads is the result of the > shuffling that does take place once in a while, organizing threads=E2=80= =99 > arrivals to the lock in a way that reduces the inter-socket lock > migration without the need to continuously modify the main queue. ..." > (page with figure 9; the paper has no page numbers) This is correct. This performance optimization deals with a small = regression that might occur at the low-medium range of contention. And just to = reiterate what the patch comment says, this optimization has nothing to do with = correctness and does not introduce any extra delays for threads already waiting in = the secondary queue. >=20 > But OTHO why this pseudo randomness? >=20 > How about deterministically treating every 100th execution differently > (it also matches "once in a while") and thus entirely removing the > pseudo randomness? Pseudo-randomness helps to avoid pathological cases where we would do = the same decision, despite having this optimization in place, for every lock = acquisition. Consider an application in which each thread cycles through X locks, = e.g., X=3D10. If we count deterministically, then for the first 9 locks we will = _always avoid doing any shuffling, missing on any opportunity for the benefit derived by the = CNA=20 approach. At the same time, for lock #10 we will always attempt to = shuffle, and so the optimization would not have any effect.=20 >=20 > Have you tried this? If so why was it worse than pseudo randomness? >=20 > (Or maybe I missed something and pseudo randomness is required for > other reasons there.) Hope this helps =E2=80=94 let me know if you have any further questions! Best, =E2=80=94 Alex= 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=-13.8 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS 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 51EFDC433ED for ; Wed, 14 Apr 2021 18:21:13 +0000 (UTC) Received: from desiato.infradead.org (desiato.infradead.org [90.155.92.199]) (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 AEAE061153 for ; Wed, 14 Apr 2021 18:21:12 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org AEAE061153 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=oracle.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+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=desiato.20200630; h=Sender:Content-Transfer-Encoding :Content-Type:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:To:References:Message-Id:Cc:Date:In-Reply-To:From: Subject:Mime-Version:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=T26fpxLIYkoafI7Tt8dM/u75XrdNOtummVegVT9hAew=; b=Y+zLPaqXfig5dkQHyS3oPvmpT 5nWKivfTgjsCcjvTVr87j9ow58rfqgYwaPy+6Aj9Su8acO6dOQ0lvdtF31Srtx/SYBkeRIe3qi4UG w1LzgIbi9ExhE51PnOAT9aJNWa+Dl+IFr72cRpg/1kLcAdq91ZM2yR2Mi9WA3SNbvA/4UzEGGRQwE 4o/HcxU+5Czzvqi7TSHgwAb96p1K70UKQkaNMISVBOEWCHaTmbGJ9oZgVqFcTJ1yYdihV2hTs3r+P +y3lnqptEI9+tubMPXxCMLsbOAWEX4/WR/R5fzueHNPCU4Bm0688n3HczcneyDOvzOhiU0rV0lX4d fUrMeUYuA==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94 #2 (Red Hat Linux)) id 1lWk6q-00DNlJ-86; Wed, 14 Apr 2021 18:19:28 +0000 Received: from bombadil.infradead.org ([2607:7c80:54:e::133]) by desiato.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lWk6X-00DNjZ-9Z for linux-arm-kernel@desiato.infradead.org; Wed, 14 Apr 2021 18:19:10 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=To:References:Message-Id: Content-Transfer-Encoding:Cc:Date:In-Reply-To:From:Subject:Mime-Version: Content-Type:Sender:Reply-To:Content-ID:Content-Description; bh=gLGuc0MbwC1hbqSzhPV007H4I1ORU4K5O+TznHWynCk=; b=VtlVUj8Jgv2ecx+PGkHE9WRntx lTmEvoerP3GC+QkCcIr0KIKqsIekZg8AXbG+M0PNmozGuearTZa37gOl/sl12Ra6bNq/whupU/g75 sxC8sDGa8Rj4tGIFQKKSWOw80iqq7aqqJ44FEEJ9tbX5jv1NgyqkJke9pSmwZOYm3pAxw8wpYXX5V 7uN4MQR2UxMBoo+iBMgbXkg9K78wirC/ibOnwh5S1MV4AO8O1ojxcUg9M2YDLUbgohMcl5rXJCZXS GHyDGzRQkMq3hvAed8OehQSV149bywkU8ko7CLhx9fRi0SJG17pd1g2jYkrROd1kkNm3lvPeNbUe+ 6Yqu3BEw==; Received: from userp2130.oracle.com ([156.151.31.86]) by bombadil.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lWk6U-0080zE-C9 for linux-arm-kernel@lists.infradead.org; Wed, 14 Apr 2021 18:19:08 +0000 Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 13EI3qhc126356; Wed, 14 Apr 2021 18:18:21 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-2020-01-29; bh=gLGuc0MbwC1hbqSzhPV007H4I1ORU4K5O+TznHWynCk=; b=PQVoeIpjkonbJIa8tkqqaN5uVs9M4jOu/Jmuk93yrCMBZQT6K2/OgDsxINiUwIVfonGf 5O4BI7+J18NE9jnx+gXsDhEvKP4SHoomiTdVqi/WFNnBQ2Ybk+sFHixT17eLhizOcgwp o0yh0//sR0+gYNyh0OpW8odEtHo/6+JIsZ2y7698Mm35lwr8HG1LERmlfh+XY1HCSsIF 1NgM5fGU05YoIqLEGgSsdUhyWr5npwdQ4cHpB9z2WGyNzLF19B4rmx911/NrhRWNyvSl fGcQEWgVZ4LosmlqKRAQsXXgk14b+VePDT6/rCC7sBA/3H0CGWKNN7Mqpano5akGM9Yx Gw== Received: from aserp3020.oracle.com (aserp3020.oracle.com [141.146.126.70]) by userp2130.oracle.com with ESMTP id 37u3erke32-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Apr 2021 18:18:21 +0000 Received: from pps.filterd (aserp3020.oracle.com [127.0.0.1]) by aserp3020.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 13EI5k3Y125745; Wed, 14 Apr 2021 18:18:17 GMT Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by aserp3020.oracle.com with ESMTP id 37unx1q3fu-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Wed, 14 Apr 2021 18:18:17 +0000 Received: from abhmp0007.oracle.com (abhmp0007.oracle.com [141.146.116.13]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id 13EII8L6015694; Wed, 14 Apr 2021 18:18:08 GMT Received: from [10.39.249.3] (/10.39.249.3) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Wed, 14 Apr 2021 11:18:07 -0700 Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\)) Subject: Re: [External] : Re: [PATCH v14 6/6] locking/qspinlock: Introduce the shuffle reduction optimization into CNA From: Alex Kogan In-Reply-To: Date: Wed, 14 Apr 2021 14:18:05 -0400 Cc: linux@armlinux.org.uk, Peter Zijlstra , Ingo Molnar , Will Deacon , 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, guohanjun@huawei.com, jglauber@marvell.com, steven.sistare@oracle.com, daniel.m.jordan@oracle.com, dave.dice@oracle.com Message-Id: <96EB342A-1343-4D71-B687-6EED27159161@oracle.com> References: <20210401153156.1165900-1-alex.kogan@oracle.com> <20210401153156.1165900-7-alex.kogan@oracle.com> To: Andreas Herrmann X-Mailer: Apple Mail (2.3608.120.23.2.4) X-Proofpoint-IMR: 1 X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=9954 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxlogscore=999 suspectscore=0 mlxscore=0 malwarescore=0 adultscore=0 bulkscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104060000 definitions=main-2104140118 X-Proofpoint-ORIG-GUID: 39TCaFnEN6owMAOcL_9f8xo3oSQ__Tm0 X-Proofpoint-GUID: 39TCaFnEN6owMAOcL_9f8xo3oSQ__Tm0 X-Proofpoint-Virus-Version: vendor=nai engine=6200 definitions=9954 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 priorityscore=1501 clxscore=1011 adultscore=0 mlxlogscore=999 bulkscore=0 malwarescore=0 spamscore=0 impostorscore=0 suspectscore=0 mlxscore=0 phishscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104060000 definitions=main-2104140118 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210414_111906_508512_8AD54186 X-CRM114-Status: GOOD ( 40.77 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org SGksIEFuZHJlYXMuCgpUaGFua3MgZm9yIHRoZSBncmVhdCBxdWVzdGlvbnMuCgo+IE9uIEFwciAx NCwgMjAyMSwgYXQgMzo0NyBBTSwgQW5kcmVhcyBIZXJybWFubiA8YWhlcnJtYW5uQHN1c2UuY29t PiB3cm90ZToKPiAKPiBPbiBUaHUsIEFwciAwMSwgMjAyMSBhdCAxMTozMTo1NkFNIC0wNDAwLCBB bGV4IEtvZ2FuIHdyb3RlOgo+PiBUaGlzIHBlcmZvcm1hbmNlIG9wdGltaXphdGlvbiBjaG9vc2Vz IHByb2JhYmlsaXN0aWNhbGx5IHRvIGF2b2lkIG1vdmluZwo+PiB0aHJlYWRzIGZyb20gdGhlIG1h aW4gcXVldWUgaW50byB0aGUgc2Vjb25kYXJ5IG9uZSB3aGVuIHRoZSBzZWNvbmRhcnkgcXVldWUK Pj4gaXMgZW1wdHkuCj4+IAo+PiBJdCBpcyBoZWxwZnVsIHdoZW4gdGhlIGxvY2sgaXMgb25seSBs aWdodGx5IGNvbnRlbmRlZC4gSW4gcGFydGljdWxhciwgaXQKPj4gbWFrZXMgQ05BIGxlc3MgZWFn ZXIgdG8gY3JlYXRlIGEgc2Vjb25kYXJ5IHF1ZXVlLCBidXQgZG9lcyBub3QgaW50cm9kdWNlCj4+ IGFueSBleHRyYSBkZWxheXMgZm9yIHRocmVhZHMgd2FpdGluZyBpbiB0aGF0IHF1ZXVlIG9uY2Ug aXQgaXMgY3JlYXRlZC4KPj4gCj4+IFNpZ25lZC1vZmYtYnk6IEFsZXggS29nYW4gPGFsZXgua29n YW5Ab3JhY2xlLmNvbT4KPj4gUmV2aWV3ZWQtYnk6IFN0ZXZlIFNpc3RhcmUgPHN0ZXZlbi5zaXN0 YXJlQG9yYWNsZS5jb20+Cj4+IFJldmlld2VkLWJ5OiBXYWltYW4gTG9uZyA8bG9uZ21hbkByZWRo YXQuY29tPgo+PiAtLS0KPj4ga2VybmVsL2xvY2tpbmcvcXNwaW5sb2NrX2NuYS5oIHwgMzkgKysr KysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKwo+PiAxIGZpbGUgY2hhbmdlZCwgMzkgaW5z ZXJ0aW9ucygrKQo+PiAKPj4gZGlmZiAtLWdpdCBhL2tlcm5lbC9sb2NraW5nL3FzcGlubG9ja19j bmEuaCBiL2tlcm5lbC9sb2NraW5nL3FzcGlubG9ja19jbmEuaAo+PiBpbmRleCAyOWMzYWJiZDNk OTQuLjk4M2M2YTQ3YTIyMSAxMDA2NDQKPj4gLS0tIGEva2VybmVsL2xvY2tpbmcvcXNwaW5sb2Nr X2NuYS5oCj4+ICsrKyBiL2tlcm5lbC9sb2NraW5nL3FzcGlubG9ja19jbmEuaAo+PiBAQCAtNSw2 ICs1LDcgQEAKPj4gCj4+ICNpbmNsdWRlIDxsaW51eC90b3BvbG9neS5oPgo+PiAjaW5jbHVkZSA8 bGludXgvc2NoZWQvcnQuaD4KPj4gKyNpbmNsdWRlIDxsaW51eC9yYW5kb20uaD4KPj4gCj4+IC8q Cj4+ICAqIEltcGxlbWVudCBhIE5VTUEtYXdhcmUgdmVyc2lvbiBvZiBNQ1MgKGFrYSBDTkEsIG9y IGNvbXBhY3QgTlVNQS1hd2FyZSBsb2NrKS4KPj4gQEAgLTg2LDYgKzg3LDM0IEBAIHN0YXRpYyBp bmxpbmUgYm9vbCBpbnRyYV9ub2RlX3RocmVzaG9sZF9yZWFjaGVkKHN0cnVjdCBjbmFfbm9kZSAq Y24pCj4+IAlyZXR1cm4gY3VycmVudF90aW1lIC0gdGhyZXNob2xkID4gMDsKPj4gfQo+PiAKPj4g Ky8qCj4+ICsgKiBDb250cm9scyB0aGUgcHJvYmFiaWxpdHkgZm9yIGVuYWJsaW5nIHRoZSBvcmRl cmluZyBvZiB0aGUgbWFpbiBxdWV1ZQo+PiArICogd2hlbiB0aGUgc2Vjb25kYXJ5IHF1ZXVlIGlz IGVtcHR5LiBUaGUgY2hvc2VuIHZhbHVlIHJlZHVjZXMgdGhlIGFtb3VudAo+PiArICogb2YgdW5u ZWNlc3Nhcnkgc2h1ZmZsaW5nIG9mIHRocmVhZHMgYmV0d2VlbiB0aGUgdHdvIHdhaXRpbmcgcXVl dWVzCj4+ICsgKiB3aGVuIHRoZSBjb250ZW50aW9uIGlzIGxvdywgd2hpbGUgcmVzcG9uZGluZyBm YXN0IGVub3VnaCBhbmQgZW5hYmxpbmcKPj4gKyAqIHRoZSBzaHVmZmxpbmcgd2hlbiB0aGUgY29u dGVudGlvbiBpcyBoaWdoLgo+PiArICovCj4+ICsjZGVmaW5lIFNIVUZGTEVfUkVEVUNUSU9OX1BS T0JfQVJHICAoNykKPiAKPiBPdXQgb2YgY3VyaW9zaXR5Ogo+IAo+IEhhdmUgeW91IHVzZWQgb3Ro ZXIgdmFsdWVzIGFuZCBkb25lIG1lYXN1cmVtZW50cyB3aGF0J3MgYW4gZWZmaWNpZW50Cj4gdmFs dWUgZm9yIFNIVUZGTEVfUkVEVUNUSU9OX1BST0JfQVJHPwpZZXMsIHdlIGRpZCB0cnkgb3RoZXIg dmFsdWVzLiBTbWFsbCB2YXJpYXRpb25zIGRvIG5vdCBjaGFuZ2UgdGhlIHJlc3VsdHMgbXVjaCwK YnV0IGlmIHlvdSBidW1wIHRoZSB2YWx1ZSBzaWduaWZpY2FudGx5IChlLmcuLCAyMCksIHlvdSBl bmQgdXAgd2l0aCBhIGxvY2sgdGhhdApoYXJkbHkgZG9lcyBhbnkgc2h1ZmZsaW5nIGFuZCB0aHVz IHBlcmZvcm1zIG9uLXBhciB3aXRoIHRoZSAoTUNTLWJhc2VkKQpiYXNlbGluZS4KCj4gTWF5YmUg SSBtaXNjYWxjdWxhdGVkIGl0LCBidXQgaWYgSSB1bmRlcnN0YW5kIGl0IGNvcnJlY3RseSB0aGlz IHZhbHVlCj4gaW1wbGllcyB0aGF0IHRoZSBwcm9wYWJpbGl0eSBpcyAwLjk5MjE4NzUgdGhhdCBi ZWxvdyBmdW5jdGlvbiByZXR1cm5zCj4gdHJ1ZS4KWW91ciBhbmFseXNpcyBpcyBjb3JyZWN0LiBJ bnR1aXRpdmVseSwgd2UgdHJpZWQgdG8ga2VlcCB0aGUgcHJvYmFiaWxpdHkgYXJvdW5kIDEtMiUs CnNvIGlmIHdlIGRvIGRlY2lkZSB0byBzaHVmZmxlIHdoZW4gd2UgZG9u4oCZdCByZWFsbHkgd2Fu dCB0byAoaS5lLiwgd2hlbiB0aGUKY29udGVudGlvbiBpcyBsb3cpLCB0aGUgb3ZlcmFsbCBvdmVy aGVhZCBvZiBzdWNoIHdyb25nIGRlY2lzaW9ucyB3b3VsZCBiZSBzbWFsbC4KCj4gCj4gTXkgcXVl c3Rpb24gaXMgcHJvYmFibHkgYW5zd2VyZWQgYnkgZm9sbG93aW5nIHN0YXRlbWVudCBmcm9tCj4g cmVmZXJlbmNlZCBwYXBlcjoKPiAKPiAiSW4gb3VyIGV4cGVyaW1lbnRzIHdpdGggdGhlIHNodWZm bGUgcmVkdWN0aW9uIG9wdGltaXphdGlvbiBlbmFibGVkLAo+IHdlIHNldCBUSFJFU0hPTEQyIHRv IDB4ZmYuIiAocGFnZSB3aXRoIGZpZ3VyZSA1KQpZZWFoLCBqdXN0IHRvIGF2b2lkIGFueSBjb25m dXNpb24g4oCUIHdlIHVzZWQgYSBkaWZmZXJlbnQgbWVjaGFuaXNtIHRvIGRyYXcKcHNldWRvLXJh bmRvbSBudW1iZXJzIGluIHRoZSBwYXBlciwgc28gdGhhdCAweGZmIG51bWJlciBpcyBub3QgZGly ZWN0bHkgCmNvbXBhcmFibGUgdG8gdGhlIHJhbmdlIG9mIHBvc3NpYmxlIHZhbHVlcyBmb3IgU0hV RkZMRV9SRURVQ1RJT05fUFJPQl9BUkcsCmJ1dCB0aGUgaWRlYSB3YXMgZXhhY3RseSB0aGUgc2Ft ZS4KCj4gCj4+ICsKPj4gKy8qIFBlci1DUFUgcHNldWRvLXJhbmRvbSBudW1iZXIgc2VlZCAqLwo+ PiArc3RhdGljIERFRklORV9QRVJfQ1BVKHUzMiwgc2VlZCk7Cj4+ICsKPj4gKy8qCj4+ICsgKiBS ZXR1cm4gZmFsc2Ugd2l0aCBwcm9iYWJpbGl0eSAxIC8gMl5AbnVtX2JpdHMuCj4+ICsgKiBJbnR1 aXRpdmVseSwgdGhlIGxhcmdlciBAbnVtX2JpdHMgdGhlIGxlc3MgbGlrZWx5IGZhbHNlIGlzIHRv IGJlIHJldHVybmVkLgo+PiArICogQG51bV9iaXRzIG11c3QgYmUgYSBudW1iZXIgYmV0d2VlbiAw IGFuZCAzMS4KPj4gKyAqLwo+PiArc3RhdGljIGJvb2wgcHJvYmFibHkodW5zaWduZWQgaW50IG51 bV9iaXRzKQo+PiArewo+PiArCXUzMiBzOwo+PiArCj4+ICsJcyA9IHRoaXNfY3B1X3JlYWQoc2Vl ZCk7Cj4+ICsJcyA9IG5leHRfcHNldWRvX3JhbmRvbTMyKHMpOwo+PiArCXRoaXNfY3B1X3dyaXRl KHNlZWQsIHMpOwo+PiArCj4+ICsJcmV0dXJuIHMgJiAoKDEgPDwgbnVtX2JpdHMpIC0gMSk7Cj4+ ICt9Cj4+ICsKPj4gc3RhdGljIHZvaWQgX19pbml0IGNuYV9pbml0X25vZGVzX3Blcl9jcHUodW5z aWduZWQgaW50IGNwdSkKPj4gewo+PiAJc3RydWN0IG1jc19zcGlubG9jayAqYmFzZSA9IHBlcl9j cHVfcHRyKCZxbm9kZXNbMF0ubWNzLCBjcHUpOwo+PiBAQCAtMjkzLDYgKzMyMiwxNiBAQCBzdGF0 aWMgX19hbHdheXNfaW5saW5lIHUzMiBjbmFfd2FpdF9oZWFkX29yX2xvY2soc3RydWN0IHFzcGlu bG9jayAqbG9jaywKPj4gewo+PiAJc3RydWN0IGNuYV9ub2RlICpjbiA9IChzdHJ1Y3QgY25hX25v ZGUgKilub2RlOwo+PiAKPj4gKwlpZiAobm9kZS0+bG9ja2VkIDw9IDEgJiYgcHJvYmFibHkoU0hV RkZMRV9SRURVQ1RJT05fUFJPQl9BUkcpKSB7Cj4gCj4gQWdhaW4gaWYgSSB1bmRlcnN0YW5kIGl0 IGNvcnJlY3RseSB3aXRoIFNIVUZGTEVfUkVEVUNUSU9OX1BST0JfQVJHPT03Cj4gaXQncyByb3Vn aGx5IDEgb3V0IG9mIDEwMCBjYXNlcyB3aGVyZSBwcm9iYWJseSgpIHJldHVybnMgZmFsc2UuCj4g Cj4gV2h5L3doZW4gaXMgdGhpcyBiZW5lZmljaWFsPwo+IAo+IEkgYXNzdW1lIGl0IGhhcyB0byBk byB3aXRoIGZvbGxvd2luZyBzdGF0ZW1lbnQgaW4gdGhlIHJlZmVyZW5jZWQKPiBwYXBlcjoKPiAK PiAiVGhlIHN1cGVyaW9yIHBlcmZvcm1hbmNlIG92ZXIgTUNTIGF0IDQgdGhyZWFkcyBpcyB0aGUg cmVzdWx0IG9mIHRoZQo+IHNodWZmbGluZyB0aGF0IGRvZXMgdGFrZSBwbGFjZSBvbmNlIGluIGEg d2hpbGUsIG9yZ2FuaXppbmcgdGhyZWFkc+KAmQo+IGFycml2YWxzIHRvIHRoZSBsb2NrIGluIGEg d2F5IHRoYXQgcmVkdWNlcyB0aGUgaW50ZXItc29ja2V0IGxvY2sKPiBtaWdyYXRpb24gd2l0aG91 dCB0aGUgbmVlZCB0byBjb250aW51b3VzbHkgbW9kaWZ5IHRoZSBtYWluIHF1ZXVlLiAuLi4iCj4g KHBhZ2Ugd2l0aCBmaWd1cmUgOTsgdGhlIHBhcGVyIGhhcyBubyBwYWdlIG51bWJlcnMpClRoaXMg aXMgY29ycmVjdC4gVGhpcyBwZXJmb3JtYW5jZSBvcHRpbWl6YXRpb24gZGVhbHMgd2l0aCBhIHNt YWxsIHJlZ3Jlc3Npb24KdGhhdCBtaWdodCBvY2N1ciBhdCB0aGUgbG93LW1lZGl1bSByYW5nZSBv ZiBjb250ZW50aW9uLiBBbmQganVzdCB0byByZWl0ZXJhdGUKd2hhdCB0aGUgcGF0Y2ggY29tbWVu dCBzYXlzLCB0aGlzIG9wdGltaXphdGlvbiBoYXMgbm90aGluZyB0byBkbyB3aXRoIGNvcnJlY3Ru ZXNzCmFuZCBkb2VzIG5vdCBpbnRyb2R1Y2UgYW55IGV4dHJhIGRlbGF5cyBmb3IgdGhyZWFkcyBh bHJlYWR5IHdhaXRpbmcgaW4gdGhlCnNlY29uZGFyeSBxdWV1ZS4KCj4gCj4gQnV0IE9USE8gd2h5 IHRoaXMgcHNldWRvIHJhbmRvbW5lc3M/Cj4gCj4gSG93IGFib3V0IGRldGVybWluaXN0aWNhbGx5 IHRyZWF0aW5nIGV2ZXJ5IDEwMHRoIGV4ZWN1dGlvbiBkaWZmZXJlbnRseQo+IChpdCBhbHNvIG1h dGNoZXMgIm9uY2UgaW4gYSB3aGlsZSIpIGFuZCB0aHVzIGVudGlyZWx5IHJlbW92aW5nIHRoZQo+ IHBzZXVkbyByYW5kb21uZXNzPwpQc2V1ZG8tcmFuZG9tbmVzcyBoZWxwcyB0byBhdm9pZCBwYXRo b2xvZ2ljYWwgY2FzZXMgd2hlcmUgd2Ugd291bGQgZG8gdGhlCnNhbWUgZGVjaXNpb24sIGRlc3Bp dGUgaGF2aW5nIHRoaXMgb3B0aW1pemF0aW9uIGluIHBsYWNlLCBmb3IgZXZlcnkgbG9jayBhY3F1 aXNpdGlvbi4KCkNvbnNpZGVyIGFuIGFwcGxpY2F0aW9uIGluIHdoaWNoIGVhY2ggdGhyZWFkIGN5 Y2xlcyB0aHJvdWdoIFggbG9ja3MsIGUuZy4sIFg9MTAuCklmIHdlIGNvdW50IGRldGVybWluaXN0 aWNhbGx5LCB0aGVuIGZvciB0aGUgZmlyc3QgOSBsb2NrcyB3ZSB3aWxsIF9hbHdheXMgYXZvaWQg ZG9pbmcKYW55IHNodWZmbGluZywgbWlzc2luZyBvbiBhbnkgb3Bwb3J0dW5pdHkgZm9yIHRoZSBi ZW5lZml0IGRlcml2ZWQgYnkgdGhlIENOQSAKYXBwcm9hY2guIEF0IHRoZSBzYW1lIHRpbWUsIGZv ciBsb2NrICMxMCB3ZSB3aWxsIGFsd2F5cyBhdHRlbXB0IHRvIHNodWZmbGUsIGFuZCBzbwp0aGUg b3B0aW1pemF0aW9uIHdvdWxkIG5vdCBoYXZlIGFueSBlZmZlY3QuIAoKPiAKPiBIYXZlIHlvdSB0 cmllZCB0aGlzPyBJZiBzbyB3aHkgd2FzIGl0IHdvcnNlIHRoYW4gcHNldWRvIHJhbmRvbW5lc3M/ Cj4gCj4gKE9yIG1heWJlIEkgbWlzc2VkIHNvbWV0aGluZyBhbmQgcHNldWRvIHJhbmRvbW5lc3Mg aXMgcmVxdWlyZWQgZm9yCj4gb3RoZXIgcmVhc29ucyB0aGVyZS4pCgpIb3BlIHRoaXMgaGVscHMg 4oCUIGxldCBtZSBrbm93IGlmIHlvdSBoYXZlIGFueSBmdXJ0aGVyIHF1ZXN0aW9ucyEKCkJlc3Qs CuKAlCBBbGV4Cl9fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f CmxpbnV4LWFybS1rZXJuZWwgbWFpbGluZyBsaXN0CmxpbnV4LWFybS1rZXJuZWxAbGlzdHMuaW5m cmFkZWFkLm9yZwpodHRwOi8vbGlzdHMuaW5mcmFkZWFkLm9yZy9tYWlsbWFuL2xpc3RpbmZvL2xp bnV4LWFybS1rZXJuZWwK