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=-11.0 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,INCLUDES_CR_TRAILER,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 8D985C433ED for ; Wed, 14 Apr 2021 00:24:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6429A613A9 for ; Wed, 14 Apr 2021 00:24:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1348174AbhDNAY0 (ORCPT ); Tue, 13 Apr 2021 20:24:26 -0400 Received: from mail.kernel.org ([198.145.29.99]:56678 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229914AbhDNAYZ (ORCPT ); Tue, 13 Apr 2021 20:24:25 -0400 Received: by mail.kernel.org (Postfix) with ESMTPSA id 2A833613B6 for ; Wed, 14 Apr 2021 00:24:05 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1618359845; bh=xovKbGed2hWLO46ZuqrlITDm4dbGTaznZbIgqZ9WyXg=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=APFSIBF7YveeiBYs2S0tL7Kh5qTOGxIRIdVCDSczSi4HEc41sLIm2c947gDziZGah TwFcbRmvki3xpDLJc125eZEr6aUv9hxXafSBQSgfsrDmuJ3C+WD8195HBLh3hmJJYI sjXtoFm+OI6GWEfCVzh7w62AlW8Y7rrpAgvpKXhbUN3WIvBsm39W0oJ4Dv9xd8czDT tSaMtB5pNO3TfDTxwij0gD/49rfzWrSpFfO7YQpMDLe7js9YZWPAfCaTNdvcQyqn4Y E9CmQWO8Ow9/lk3xRX2T6NGwQ+n64bKbcDdQWCPSQsQ+0ZYre1hmST2ry+Wt/vVK0C UpcMlWI2b858w== Received: by mail-lf1-f51.google.com with SMTP id e14so17440266lfn.11 for ; Tue, 13 Apr 2021 17:24:05 -0700 (PDT) X-Gm-Message-State: AOAM531kKhDkdBK3dhLmN4OHgMkp8OzQ12gQETHaK7K8afp/yhwGnqmw ByCEr7I1fmSHaxOx45FTayXiiRCouibOj3AqkWI= X-Google-Smtp-Source: ABdhPJygo3R6B8xRNxS/T5OobQlEyh5OWixS+23KYstwEOK86NT5oa4jvbiep9TH6hZHgQWozKwBlPTidWdfKXC3uEg= X-Received: by 2002:a05:6512:3ca7:: with SMTP id h39mr25005082lfv.346.1618359843478; Tue, 13 Apr 2021 17:24:03 -0700 (PDT) MIME-Version: 1.0 References: <20210413093059.GB15806@arm.com> In-Reply-To: <20210413093059.GB15806@arm.com> From: Guo Ren Date: Wed, 14 Apr 2021 08:23:51 +0800 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH] riscv: locks: introduce ticket-based spinlock implementation To: Catalin Marinas Cc: =?UTF-8?Q?Christoph_M=C3=BCllner?= , Peter Zijlstra , Palmer Dabbelt , Anup Patel , linux-riscv , Linux Kernel Mailing List , Guo Ren , Will Deacon , Arnd Bergmann Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Apr 13, 2021 at 5:31 PM Catalin Marinas w= rote: > > On Tue, Apr 13, 2021 at 11:22:40AM +0200, Christoph M=C3=BCllner wrote: > > On Tue, Apr 13, 2021 at 10:03 AM Peter Zijlstra = wrote: > > > On Mon, Apr 12, 2021 at 11:54:55PM +0200, Christoph M=C3=BCllner wrot= e: > > > > On Mon, Apr 12, 2021 at 7:33 PM Palmer Dabbelt = wrote: > > > > > My plan is to add a generic ticket-based lock, which can be selec= ted at > > > > > compile time. It'll have no architecture dependencies (though it= 'll > > > > > likely have some hooks for architectures that can make this go fa= ster). > > > > > Users can then just pick which spinlock flavor they want, with th= e idea > > > > > being that smaller systems will perform better with ticket locks = and > > > > > larger systems will perform better with queued locks. The main g= oal > > > > > here is to give the less widely used architectures an easy way to= have > > > > > fair locks, as right now we've got a lot of code duplication beca= use any > > > > > architecture that wants ticket locks has to do it themselves. > > > > > > > > In the case of LL/SC sequences, we have a maximum of 16 instruction= s > > > > on RISC-V. My concern with a pure-C implementation would be that > > > > we cannot guarantee this (e.g. somebody wants to compile with -O0) > > > > and I don't know of a way to abort the build in case this limit exc= eeds. > > > > Therefore I have preferred inline assembly for OpenSBI (my initial = idea > > > > was to use closure-like LL/SC macros, where you can write the loop > > > > in form of C code). > > > > > > For ticket locks you really only needs atomic_fetch_add() and > > > smp_store_release() and an architectural guarantees that the > > > atomic_fetch_add() has fwd progress under contention and that a sub-w= ord > > > store (through smp_store_release()) will fail the SC. > > > > > > Then you can do something like: > > > > > > void lock(atomic_t *lock) > > > { > > > u32 val =3D atomic_fetch_add(1<<16, lock); /* SC, gives us RC= sc */ > > > u16 ticket =3D val >> 16; > > > > > > for (;;) { > > > if (ticket =3D=3D (u16)val) > > > break; > > > cpu_relax(); > > > val =3D atomic_read_acquire(lock); > > > } > > > } > > > > > > void unlock(atomic_t *lock) > > > { > > > u16 *ptr =3D (u16 *)lock + (!!__BIG_ENDIAN__); > > > u32 val =3D atomic_read(lock); > > > > > > smp_store_release(ptr, (u16)val + 1); > > > } > > > > > > That's _almost_ as simple as a test-and-set :-) It isn't quite optima= l > > > on x86 for not being allowed to use a memop on unlock, since its bein= g > > > forced into a load-store because of all the volatile, but whatever. > > > > What about trylock()? > > I.e. one could implement trylock() without a loop, by letting > > trylock() fail if the SC fails. > > That looks safe on first view, but nobody does this right now. I think it's safe for riscv LR/SC, because in spec A 8.3 section: "As a consequence of the eventuality guarantee, if some harts in an execution environment are executing constrained LR/SC loops, and no other harts or devices in the execution environment execute an unconditional store or AMO to that reservation set, then at least one hart will eventually exit its constrained LR/SC loop." So it guarantees LR/SC pair: CPU0 CPU1 =3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D LR addr1 LR addr1 SC addr1 // guarantee success. SC addr1 But not guarantee, another hart unconditional store (which I mentioned befo= re): u32 a =3D 0x55aa66bb; u16 *ptr =3D &a; CPU0 CPU1 =3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D xchg16(ptr, new) while(1) WRITE_ONCE(*(ptr + 1), x); > > Not familiar with RISC-V but I'd recommend that a trylock only fails if > the lock is locked (after LR). A SC may fail for other reasons > (cacheline eviction; depending on the microarchitecture) even if the > lock is unlocked. At least on arm64 we had this issue with an > implementation having a tendency to always fail the first STXR. I think it's a broken implementation for riscv. SC couldn't fail by cache line bouncing and only could fail by another real write. That means the HW implementation should use a per-hart address monitor not just grab the cache line into the exclusive state without lockdown the SNOOP channel. I think the implementation of LR/SC you mentioned is a gambling style but broke the riscv spec. Is the patch of Will's would fix up the problem you mentioned? ---- commit 9bb17be062de6f5a9c9643258951aa0935652ec3 Author: Will Deacon Date: Tue Jul 2 14:54:33 2013 +0100 ARM: locks: prefetch the destination word for write prior to strex The cost of changing a cacheline from shared to exclusive state can be significant, especially when this is triggered by an exclusive store, since it may result in having to retry the transaction. This patch prefixes our {spin,read,write}_[try]lock implementations wit= h pldw instructions (on CPUs which support them) to try and grab the line in exclusive state from the start. arch_rwlock_t is changed to avoid using a volatile member, since this generates compiler warnings when falling back on the __builtin_prefetch intrinsic which expects a const void * argument. Acked-by: Nicolas Pitre Signed-off-by: Will Deacon ---- In the end, I want to conclude my suggestions here: - Using ticket-lock as default - Using ARCH_USE_QUEUED_SPINLOCKS_XCHG32 for riscv qspinlock - Disable xhg16/cmxchg16 and any sub-word atomic primitive in riscv -- Best Regards Guo Ren ML: https://lore.kernel.org/linux-csky/ 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=-9.0 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,INCLUDES_CR_TRAILER,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 BF65BC433B4 for ; Wed, 14 Apr 2021 00:24:45 +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 383B66128E for ; Wed, 14 Apr 2021 00:24:45 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 383B66128E Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-riscv-bounces+linux-riscv=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:Cc:To:Subject:Message-ID:Date:From:In-Reply-To: References:MIME-Version:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=XcushlAL9AWYSekOu5pQTwAQ4UTxRUH6o3k6igwjji8=; b=EBFp+WUBcwn/BiPCTiGUBJwNk IqaUVaZFV89L2J+FXgTu2rGlNhArTJCSnAApJlLOLKVBugjIp1UW/7/sTO4+VxWrk4pncBHbS9kyt MWK1Xz+k/Gje5QQid5pBFo7umH4d+0KQnlJICD2xNaZwduCZk4wIwmTyK2x8P4/3ZwqIRt5zdYmsu a3wwjVkqs3vpPYcXRWYZnt9uf1TrSHCU6Sqer7lM+1Ro+01c1vj2eGbddyG+OIMZbFRDL+TVgEbj1 RwWe7XM50diLut062SEHb5lqbwQTFr6RgKkx5jcPN6VVYDzwMWp78KB82QmNGC/5XIDMs6AJ4sCME PwV+4b9Nw==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94 #2 (Red Hat Linux)) id 1lWTKN-00Avvs-M4; Wed, 14 Apr 2021 00:24:20 +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 1lWTKD-00AvuY-GM for linux-riscv@desiato.infradead.org; Wed, 14 Apr 2021 00:24:11 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: Content-Type:Cc:To:Subject:Message-ID:Date:From:In-Reply-To:References: MIME-Version:Sender:Reply-To:Content-ID:Content-Description; bh=CUbaMpgqOTeGscAmBT+v8HSRuAKZHpMwxHzLXqOJAiY=; b=MLDegqVuuky7OxpQpez5DF3/4f 8Wl5M0GQ3+VISzNr1hw7K/BT1GtlIP/sifeRA9Zu2ucqJ5lRPCV1UjxynmcHKTg5tYF8nHC2PNo6b igF8PI3V85nfVvsaDtLDXlMEg+LrvTTLHL0litFSliLuhO0wSCZaYsfvMq/7r7b+3coqjKjfjQg3i j0tpHtk99YOzHOAEQ3eqKKS02yC4YxQebGdKIeM1hetlcXXPivrfU33zC2YjYIrUkipTTdc2J0uqq Uv7l66GmLgJMgirCg/98ySa9yKH3DHH5cJTUR9P455Q8uj/TvYrXx9IVEF3SI7dX0i7SgK6Hr1etg H+tjnYGw==; Received: from mail.kernel.org ([198.145.29.99]) by bombadil.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lWTK9-007P1r-Lv for linux-riscv@lists.infradead.org; Wed, 14 Apr 2021 00:24:07 +0000 Received: by mail.kernel.org (Postfix) with ESMTPSA id 2CDD7613C0 for ; Wed, 14 Apr 2021 00:24:05 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1618359845; bh=xovKbGed2hWLO46ZuqrlITDm4dbGTaznZbIgqZ9WyXg=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=APFSIBF7YveeiBYs2S0tL7Kh5qTOGxIRIdVCDSczSi4HEc41sLIm2c947gDziZGah TwFcbRmvki3xpDLJc125eZEr6aUv9hxXafSBQSgfsrDmuJ3C+WD8195HBLh3hmJJYI sjXtoFm+OI6GWEfCVzh7w62AlW8Y7rrpAgvpKXhbUN3WIvBsm39W0oJ4Dv9xd8czDT tSaMtB5pNO3TfDTxwij0gD/49rfzWrSpFfO7YQpMDLe7js9YZWPAfCaTNdvcQyqn4Y E9CmQWO8Ow9/lk3xRX2T6NGwQ+n64bKbcDdQWCPSQsQ+0ZYre1hmST2ry+Wt/vVK0C UpcMlWI2b858w== Received: by mail-lf1-f43.google.com with SMTP id x13so20111460lfr.2 for ; Tue, 13 Apr 2021 17:24:05 -0700 (PDT) X-Gm-Message-State: AOAM533snVLX5A7325m5bZmx7IByq/sNnZ6ev7xXkH6/oRJH0TzPYBxY uQ+39WShDbPEfWxAN3bSPPxfLbQHUxBoZSN1Rxo= X-Google-Smtp-Source: ABdhPJygo3R6B8xRNxS/T5OobQlEyh5OWixS+23KYstwEOK86NT5oa4jvbiep9TH6hZHgQWozKwBlPTidWdfKXC3uEg= X-Received: by 2002:a05:6512:3ca7:: with SMTP id h39mr25005082lfv.346.1618359843478; Tue, 13 Apr 2021 17:24:03 -0700 (PDT) MIME-Version: 1.0 References: <20210413093059.GB15806@arm.com> In-Reply-To: <20210413093059.GB15806@arm.com> From: Guo Ren Date: Wed, 14 Apr 2021 08:23:51 +0800 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH] riscv: locks: introduce ticket-based spinlock implementation To: Catalin Marinas Cc: =?UTF-8?Q?Christoph_M=C3=BCllner?= , Peter Zijlstra , Palmer Dabbelt , Anup Patel , linux-riscv , Linux Kernel Mailing List , Guo Ren , Will Deacon , Arnd Bergmann X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210413_172405_784083_3521F4D1 X-CRM114-Status: GOOD ( 44.84 ) X-BeenThere: linux-riscv@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-riscv" Errors-To: linux-riscv-bounces+linux-riscv=archiver.kernel.org@lists.infradead.org T24gVHVlLCBBcHIgMTMsIDIwMjEgYXQgNTozMSBQTSBDYXRhbGluIE1hcmluYXMgPGNhdGFsaW4u bWFyaW5hc0Bhcm0uY29tPiB3cm90ZToKPgo+IE9uIFR1ZSwgQXByIDEzLCAyMDIxIGF0IDExOjIy OjQwQU0gKzAyMDAsIENocmlzdG9waCBNw7xsbG5lciB3cm90ZToKPiA+IE9uIFR1ZSwgQXByIDEz LCAyMDIxIGF0IDEwOjAzIEFNIFBldGVyIFppamxzdHJhIDxwZXRlcnpAaW5mcmFkZWFkLm9yZz4g d3JvdGU6Cj4gPiA+IE9uIE1vbiwgQXByIDEyLCAyMDIxIGF0IDExOjU0OjU1UE0gKzAyMDAsIENo cmlzdG9waCBNw7xsbG5lciB3cm90ZToKPiA+ID4gPiBPbiBNb24sIEFwciAxMiwgMjAyMSBhdCA3 OjMzIFBNIFBhbG1lciBEYWJiZWx0IDxwYWxtZXJAZGFiYmVsdC5jb20+IHdyb3RlOgo+ID4gPiA+ ID4gTXkgcGxhbiBpcyB0byBhZGQgYSBnZW5lcmljIHRpY2tldC1iYXNlZCBsb2NrLCB3aGljaCBj YW4gYmUgc2VsZWN0ZWQgYXQKPiA+ID4gPiA+IGNvbXBpbGUgdGltZS4gIEl0J2xsIGhhdmUgbm8g YXJjaGl0ZWN0dXJlIGRlcGVuZGVuY2llcyAodGhvdWdoIGl0J2xsCj4gPiA+ID4gPiBsaWtlbHkg aGF2ZSBzb21lIGhvb2tzIGZvciBhcmNoaXRlY3R1cmVzIHRoYXQgY2FuIG1ha2UgdGhpcyBnbyBm YXN0ZXIpLgo+ID4gPiA+ID4gVXNlcnMgY2FuIHRoZW4ganVzdCBwaWNrIHdoaWNoIHNwaW5sb2Nr IGZsYXZvciB0aGV5IHdhbnQsIHdpdGggdGhlIGlkZWEKPiA+ID4gPiA+IGJlaW5nIHRoYXQgc21h bGxlciBzeXN0ZW1zIHdpbGwgcGVyZm9ybSBiZXR0ZXIgd2l0aCB0aWNrZXQgbG9ja3MgYW5kCj4g PiA+ID4gPiBsYXJnZXIgc3lzdGVtcyB3aWxsIHBlcmZvcm0gYmV0dGVyIHdpdGggcXVldWVkIGxv Y2tzLiAgVGhlIG1haW4gZ29hbAo+ID4gPiA+ID4gaGVyZSBpcyB0byBnaXZlIHRoZSBsZXNzIHdp ZGVseSB1c2VkIGFyY2hpdGVjdHVyZXMgYW4gZWFzeSB3YXkgdG8gaGF2ZQo+ID4gPiA+ID4gZmFp ciBsb2NrcywgYXMgcmlnaHQgbm93IHdlJ3ZlIGdvdCBhIGxvdCBvZiBjb2RlIGR1cGxpY2F0aW9u IGJlY2F1c2UgYW55Cj4gPiA+ID4gPiBhcmNoaXRlY3R1cmUgdGhhdCB3YW50cyB0aWNrZXQgbG9j a3MgaGFzIHRvIGRvIGl0IHRoZW1zZWx2ZXMuCj4gPiA+ID4KPiA+ID4gPiBJbiB0aGUgY2FzZSBv ZiBMTC9TQyBzZXF1ZW5jZXMsIHdlIGhhdmUgYSBtYXhpbXVtIG9mIDE2IGluc3RydWN0aW9ucwo+ ID4gPiA+IG9uIFJJU0MtVi4gTXkgY29uY2VybiB3aXRoIGEgcHVyZS1DIGltcGxlbWVudGF0aW9u IHdvdWxkIGJlIHRoYXQKPiA+ID4gPiB3ZSBjYW5ub3QgZ3VhcmFudGVlIHRoaXMgKGUuZy4gc29t ZWJvZHkgd2FudHMgdG8gY29tcGlsZSB3aXRoIC1PMCkKPiA+ID4gPiBhbmQgSSBkb24ndCBrbm93 IG9mIGEgd2F5IHRvIGFib3J0IHRoZSBidWlsZCBpbiBjYXNlIHRoaXMgbGltaXQgZXhjZWVkcy4K PiA+ID4gPiBUaGVyZWZvcmUgSSBoYXZlIHByZWZlcnJlZCBpbmxpbmUgYXNzZW1ibHkgZm9yIE9w ZW5TQkkgKG15IGluaXRpYWwgaWRlYQo+ID4gPiA+IHdhcyB0byB1c2UgY2xvc3VyZS1saWtlIExM L1NDIG1hY3Jvcywgd2hlcmUgeW91IGNhbiB3cml0ZSB0aGUgbG9vcAo+ID4gPiA+IGluIGZvcm0g b2YgQyBjb2RlKS4KPiA+ID4KPiA+ID4gRm9yIHRpY2tldCBsb2NrcyB5b3UgcmVhbGx5IG9ubHkg bmVlZHMgYXRvbWljX2ZldGNoX2FkZCgpIGFuZAo+ID4gPiBzbXBfc3RvcmVfcmVsZWFzZSgpIGFu ZCBhbiBhcmNoaXRlY3R1cmFsIGd1YXJhbnRlZXMgdGhhdCB0aGUKPiA+ID4gYXRvbWljX2ZldGNo X2FkZCgpIGhhcyBmd2QgcHJvZ3Jlc3MgdW5kZXIgY29udGVudGlvbiBhbmQgdGhhdCBhIHN1Yi13 b3JkCj4gPiA+IHN0b3JlICh0aHJvdWdoIHNtcF9zdG9yZV9yZWxlYXNlKCkpIHdpbGwgZmFpbCB0 aGUgU0MuCj4gPiA+Cj4gPiA+IFRoZW4geW91IGNhbiBkbyBzb21ldGhpbmcgbGlrZToKPiA+ID4K PiA+ID4gdm9pZCBsb2NrKGF0b21pY190ICpsb2NrKQo+ID4gPiB7Cj4gPiA+ICAgICAgICAgdTMy IHZhbCA9IGF0b21pY19mZXRjaF9hZGQoMTw8MTYsIGxvY2spOyAvKiBTQywgZ2l2ZXMgdXMgUkNz YyAqLwo+ID4gPiAgICAgICAgIHUxNiB0aWNrZXQgPSB2YWwgPj4gMTY7Cj4gPiA+Cj4gPiA+ICAg ICAgICAgZm9yICg7Oykgewo+ID4gPiAgICAgICAgICAgICAgICAgaWYgKHRpY2tldCA9PSAodTE2 KXZhbCkKPiA+ID4gICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7Cj4gPiA+ICAgICAgICAg ICAgICAgICBjcHVfcmVsYXgoKTsKPiA+ID4gICAgICAgICAgICAgICAgIHZhbCA9IGF0b21pY19y ZWFkX2FjcXVpcmUobG9jayk7Cj4gPiA+ICAgICAgICAgfQo+ID4gPiB9Cj4gPiA+Cj4gPiA+IHZv aWQgdW5sb2NrKGF0b21pY190ICpsb2NrKQo+ID4gPiB7Cj4gPiA+ICAgICAgICAgdTE2ICpwdHIg PSAodTE2ICopbG9jayArICghIV9fQklHX0VORElBTl9fKTsKPiA+ID4gICAgICAgICB1MzIgdmFs ID0gYXRvbWljX3JlYWQobG9jayk7Cj4gPiA+Cj4gPiA+ICAgICAgICAgc21wX3N0b3JlX3JlbGVh c2UocHRyLCAodTE2KXZhbCArIDEpOwo+ID4gPiB9Cj4gPiA+Cj4gPiA+IFRoYXQncyBfYWxtb3N0 XyBhcyBzaW1wbGUgYXMgYSB0ZXN0LWFuZC1zZXQgOi0pIEl0IGlzbid0IHF1aXRlIG9wdGltYWwK PiA+ID4gb24geDg2IGZvciBub3QgYmVpbmcgYWxsb3dlZCB0byB1c2UgYSBtZW1vcCBvbiB1bmxv Y2ssIHNpbmNlIGl0cyBiZWluZwo+ID4gPiBmb3JjZWQgaW50byBhIGxvYWQtc3RvcmUgYmVjYXVz ZSBvZiBhbGwgdGhlIHZvbGF0aWxlLCBidXQgd2hhdGV2ZXIuCj4gPgo+ID4gV2hhdCBhYm91dCB0 cnlsb2NrKCk/Cj4gPiBJLmUuIG9uZSBjb3VsZCBpbXBsZW1lbnQgdHJ5bG9jaygpIHdpdGhvdXQg YSBsb29wLCBieSBsZXR0aW5nCj4gPiB0cnlsb2NrKCkgZmFpbCBpZiB0aGUgU0MgZmFpbHMuCj4g PiBUaGF0IGxvb2tzIHNhZmUgb24gZmlyc3QgdmlldywgYnV0IG5vYm9keSBkb2VzIHRoaXMgcmln aHQgbm93LgpJIHRoaW5rIGl0J3Mgc2FmZSBmb3IgcmlzY3YgTFIvU0MsIGJlY2F1c2UgaW4gc3Bl YyBBIDguMyBzZWN0aW9uOgoiQXMgYSBjb25zZXF1ZW5jZSBvZiB0aGUgZXZlbnR1YWxpdHkgZ3Vh cmFudGVlLCBpZiBzb21lIGhhcnRzIGluIGFuCmV4ZWN1dGlvbiBlbnZpcm9ubWVudCBhcmUgZXhl Y3V0aW5nIGNvbnN0cmFpbmVkIExSL1NDIGxvb3BzLCBhbmQgbm8Kb3RoZXIgaGFydHMgb3IgZGV2 aWNlcyBpbiB0aGUgZXhlY3V0aW9uIGVudmlyb25tZW50IGV4ZWN1dGUgYW4KdW5jb25kaXRpb25h bCBzdG9yZSBvciBBTU8gdG8gdGhhdCByZXNlcnZhdGlvbiBzZXQsIHRoZW4gYXQgbGVhc3Qgb25l CmhhcnQgd2lsbCBldmVudHVhbGx5IGV4aXQgaXRzIGNvbnN0cmFpbmVkIExSL1NDIGxvb3AuIgoK U28gaXQgZ3VhcmFudGVlcyBMUi9TQyBwYWlyOgoKQ1BVMCAgICAgICAgICAgICAgICAgICBDUFUx Cj09PT09PT0gICAgICAgICAgICAgPT09PT09PQpMUiBhZGRyMQogICAgICAgICAgICAgICAgICAg ICAgICAgICAgTFIgYWRkcjEKICAgICAgICAgICAgICAgICAgICAgICAgICAgIFNDIGFkZHIxIC8v IGd1YXJhbnRlZSBzdWNjZXNzLgpTQyBhZGRyMQoKQnV0IG5vdCBndWFyYW50ZWUsIGFub3RoZXIg aGFydCB1bmNvbmRpdGlvbmFsIHN0b3JlICh3aGljaCBJIG1lbnRpb25lZCBiZWZvcmUpOgp1MzIg YSA9IDB4NTVhYTY2YmI7CnUxNiAqcHRyID0gJmE7CgpDUFUwICAgICAgICAgICAgICAgICAgICAg ICBDUFUxCj09PT09PT09PSAgICAgICAgICAgICA9PT09PT09PT0KeGNoZzE2KHB0ciwgbmV3KSAg ICAgd2hpbGUoMSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgV1JJVEVfT05D RSgqKHB0ciArIDEpLCB4KTsKCgoKPgo+IE5vdCBmYW1pbGlhciB3aXRoIFJJU0MtViBidXQgSSdk IHJlY29tbWVuZCB0aGF0IGEgdHJ5bG9jayBvbmx5IGZhaWxzIGlmCj4gdGhlIGxvY2sgaXMgbG9j a2VkIChhZnRlciBMUikuIEEgU0MgbWF5IGZhaWwgZm9yIG90aGVyIHJlYXNvbnMKPiAoY2FjaGVs aW5lIGV2aWN0aW9uOyBkZXBlbmRpbmcgb24gdGhlIG1pY3JvYXJjaGl0ZWN0dXJlKSBldmVuIGlm IHRoZQo+IGxvY2sgaXMgdW5sb2NrZWQuIEF0IGxlYXN0IG9uIGFybTY0IHdlIGhhZCB0aGlzIGlz c3VlIHdpdGggYW4KPiBpbXBsZW1lbnRhdGlvbiBoYXZpbmcgYSB0ZW5kZW5jeSB0byBhbHdheXMg ZmFpbCB0aGUgZmlyc3QgU1RYUi4KCkkgdGhpbmsgaXQncyBhIGJyb2tlbiBpbXBsZW1lbnRhdGlv biBmb3IgcmlzY3YuIFNDIGNvdWxkbid0IGZhaWwgYnkKY2FjaGUgbGluZSBib3VuY2luZyBhbmQg b25seSBjb3VsZCBmYWlsIGJ5IGFub3RoZXIgcmVhbCB3cml0ZS4KVGhhdCBtZWFucyB0aGUgSFcg aW1wbGVtZW50YXRpb24gc2hvdWxkIHVzZSBhIHBlci1oYXJ0IGFkZHJlc3MgbW9uaXRvcgpub3Qg anVzdCBncmFiIHRoZSBjYWNoZSBsaW5lIGludG8gdGhlIGV4Y2x1c2l2ZSBzdGF0ZSB3aXRob3V0 IGxvY2tkb3duCnRoZSBTTk9PUCBjaGFubmVsLgpJIHRoaW5rIHRoZSBpbXBsZW1lbnRhdGlvbiBv ZiBMUi9TQyB5b3UgbWVudGlvbmVkIGlzIGEgZ2FtYmxpbmcgc3R5bGUKYnV0IGJyb2tlIHRoZSBy aXNjdiBzcGVjLgoKSXMgdGhlIHBhdGNoIG9mIFdpbGwncyB3b3VsZCBmaXggdXAgdGhlIHByb2Js ZW0geW91IG1lbnRpb25lZD8KLS0tLQpjb21taXQgOWJiMTdiZTA2MmRlNmY1YTljOTY0MzI1ODk1 MWFhMDkzNTY1MmVjMwpBdXRob3I6IFdpbGwgRGVhY29uIDx3aWxsLmRlYWNvbkBhcm0uY29tPgpE YXRlOiAgIFR1ZSBKdWwgMiAxNDo1NDozMyAyMDEzICswMTAwCgogICAgQVJNOiBsb2NrczogcHJl ZmV0Y2ggdGhlIGRlc3RpbmF0aW9uIHdvcmQgZm9yIHdyaXRlIHByaW9yIHRvIHN0cmV4CgogICAg VGhlIGNvc3Qgb2YgY2hhbmdpbmcgYSBjYWNoZWxpbmUgZnJvbSBzaGFyZWQgdG8gZXhjbHVzaXZl IHN0YXRlIGNhbiBiZQogICAgc2lnbmlmaWNhbnQsIGVzcGVjaWFsbHkgd2hlbiB0aGlzIGlzIHRy aWdnZXJlZCBieSBhbiBleGNsdXNpdmUgc3RvcmUsCiAgICBzaW5jZSBpdCBtYXkgcmVzdWx0IGlu IGhhdmluZyB0byByZXRyeSB0aGUgdHJhbnNhY3Rpb24uCgogICAgVGhpcyBwYXRjaCBwcmVmaXhl cyBvdXIge3NwaW4scmVhZCx3cml0ZX1fW3RyeV1sb2NrIGltcGxlbWVudGF0aW9ucyB3aXRoCiAg ICBwbGR3IGluc3RydWN0aW9ucyAob24gQ1BVcyB3aGljaCBzdXBwb3J0IHRoZW0pIHRvIHRyeSBh bmQgZ3JhYiB0aGUgbGluZQogICAgaW4gZXhjbHVzaXZlIHN0YXRlIGZyb20gdGhlIHN0YXJ0LiBh cmNoX3J3bG9ja190IGlzIGNoYW5nZWQgdG8gYXZvaWQKICAgIHVzaW5nIGEgdm9sYXRpbGUgbWVt YmVyLCBzaW5jZSB0aGlzIGdlbmVyYXRlcyBjb21waWxlciB3YXJuaW5ncyB3aGVuCiAgICBmYWxs aW5nIGJhY2sgb24gdGhlIF9fYnVpbHRpbl9wcmVmZXRjaCBpbnRyaW5zaWMgd2hpY2ggZXhwZWN0 cyBhIGNvbnN0CiAgICB2b2lkICogYXJndW1lbnQuCgogICAgQWNrZWQtYnk6IE5pY29sYXMgUGl0 cmUgPG5pY29AbGluYXJvLm9yZz4KICAgIFNpZ25lZC1vZmYtYnk6IFdpbGwgRGVhY29uIDx3aWxs LmRlYWNvbkBhcm0uY29tPgotLS0tCgpJbiB0aGUgZW5kLCBJIHdhbnQgdG8gY29uY2x1ZGUgbXkg c3VnZ2VzdGlvbnMgaGVyZToKIC0gVXNpbmcgdGlja2V0LWxvY2sgYXMgZGVmYXVsdAogLSBVc2lu ZyBBUkNIX1VTRV9RVUVVRURfU1BJTkxPQ0tTX1hDSEczMiBmb3IgcmlzY3YgcXNwaW5sb2NrCiAt IERpc2FibGUgeGhnMTYvY214Y2hnMTYgYW5kIGFueSBzdWItd29yZCBhdG9taWMgcHJpbWl0aXZl IGluIHJpc2N2CgotLQpCZXN0IFJlZ2FyZHMKIEd1byBSZW4KCk1MOiBodHRwczovL2xvcmUua2Vy bmVsLm9yZy9saW51eC1jc2t5LwoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX19fX18KbGludXgtcmlzY3YgbWFpbGluZyBsaXN0CmxpbnV4LXJpc2N2QGxpc3RzLmlu ZnJhZGVhZC5vcmcKaHR0cDovL2xpc3RzLmluZnJhZGVhZC5vcmcvbWFpbG1hbi9saXN0aW5mby9s aW51eC1yaXNjdgo=