From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on archive.lwn.net X-Spam-Level: X-Spam-Status: No, score=-5.6 required=5.0 tests=DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI, T_DKIM_INVALID autolearn=unavailable autolearn_force=no version=3.4.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by archive.lwn.net (Postfix) with ESMTP id 6F1307D043 for ; Tue, 19 Jun 2018 08:27:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756369AbeFSI0d (ORCPT ); Tue, 19 Jun 2018 04:26:33 -0400 Received: from mail-co1nam03on0057.outbound.protection.outlook.com ([104.47.40.57]:50284 "EHLO NAM03-CO1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1756648AbeFSI0J (ORCPT ); Tue, 19 Jun 2018 04:26:09 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vmware.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=qXHTnjpcdF7loCMrjXrOv/Ehrd7fN/tm5TYDUUMNPgY=; b=hpLdSgoMrxcBZd8KGOFIDSaIG17UOT5fAnMZejZmaH/+w63VYuq5uSP7M+2ReEjuhSJi3Lnj/esA3PhGSdJ8RawlthKOQYnbBOe4pllFg/Ex47TebNACr82PabgLhctnmnKuDBYMWGr9ZAR7CUMb8eS3mDUO68LPwSSMJwkt828= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=thellstrom@vmware.com; Received: from localhost.vmware.com (155.4.205.56) by DM6PR05MB4585.namprd05.prod.outlook.com (2603:10b6:5:9f::22) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.884.16; Tue, 19 Jun 2018 08:25:53 +0000 From: Thomas Hellstrom To: dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, peterz@infradead.org Cc: linux-graphics-maintainer@vmware.com, pv-drivers@vmware.com, Thomas Hellstrom , Ingo Molnar , Jonathan Corbet , Gustavo Padovan , Maarten Lankhorst , Sean Paul , David Airlie , Davidlohr Bueso , "Paul E. McKenney" , Josh Triplett , Thomas Gleixner , Kate Stewart , Philippe Ombredanne , Greg Kroah-Hartman , linux-doc@vger.kernel.org, linux-media@vger.kernel.org, linaro-mm-sig@lists.linaro.org Subject: [PATCH v4 2/3] locking: Implement an algorithm choice for Wound-Wait mutexes Date: Tue, 19 Jun 2018 10:24:44 +0200 Message-Id: <20180619082445.11062-3-thellstrom@vmware.com> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180619082445.11062-1-thellstrom@vmware.com> References: <20180619082445.11062-1-thellstrom@vmware.com> MIME-Version: 1.0 Content-Type: text/plain X-Originating-IP: [155.4.205.56] X-ClientProxiedBy: CO2PR04CA0136.namprd04.prod.outlook.com (2603:10b6:104::14) To DM6PR05MB4585.namprd05.prod.outlook.com (2603:10b6:5:9f::22) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: e0a09575-28bd-496c-cbc5-08d5d5be490a X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:(7020095)(4652020)(4534165)(4627221)(201703031133081)(201702281549075)(5600026)(711020)(2017052603328)(7153060)(7193020);SRVR:DM6PR05MB4585; X-Microsoft-Exchange-Diagnostics: 1;DM6PR05MB4585;3:sDk2SUOqrxTiIVWae7gnDsSR+0hLL1bS9M7rddfNs6tPYpNiN/2bL3FvJEt9ZuEeHUSwMIyJXiG8bVVO4BnIpwL1syTSb7vrfhFxSszUjyUEs/3f+d0zil1stM5OKkrIA8+qfmicoa5TI6U81Jb9bMs1YBvBKKHRDGobRKRgIMBG53oRLO5zExNCHS2jcX51f55E5hgP+iMUi1tow9X6RRf4coSIgZ0gCP1VTzXM4KmFnp0GpYwcJIywPMLRM6B3;25:aIggr8w02nFkGjK2kE5UuRcy6dPMNcs3pyVRI2a1nZRH2t/JyvgZDXqx5J0jctIj8N9wHwLCHYa9ABHCcJpIPEIdXDC2xxhJjqJguHfR7K3UgwkjRemGlsuthqJr2phubi0qA6cysOF+bVTKc+QZn+Wo1NQVTjnpHzjHhk9brxXvosrEh6D0ZT7YBjqTURNUJ2XAiho2I/cpSYkhqUuxn07RyFRv3AQTTSAm+K7fXdQ/Mdyd9x83vjyZWCY+7YfLM7bPwhFcPUlEkGF2A5lxPXnY9JP3DdrPzVDxScvaxmEAnWZisybkExm7SYk4g2H3lknW1LeKuxRet6k/5xPIQQ==;31:I5TJfuemt4l2kPX5qt+ikFDAT1AaCe6Aq45XqvARvbxJd6tW7xy3REHrYmDsPNarGwBoScsYEzIxhvKyBBpn1XgpPpfERV/6/LQpj3nQlT01l4WhwjpQHSg5L7QYwz1eDzWXLq2k2iwGYHfM3uEn2N7tn3zvFGROflqdHt0M0d/d925Ev5FC98lAHWqiU3Ns1XyblwT7nwD75FDm1A6oBkCFelZaytXMow78mjye+Zg= X-MS-TrafficTypeDiagnostic: DM6PR05MB4585: X-LD-Processed: b39138ca-3cee-4b4a-a4d6-cd83d9dd62f0,ExtAddr X-Microsoft-Exchange-Diagnostics: 1;DM6PR05MB4585;20:Y1yw7gR/eTgb8wlj4Rko/xkDAwQjjkGaH71MikrGiOfkLnqSM/4EBL4USvJ9Sn5EOAAyzjdA+LwjH44dF7xy5rNDl7+CYcN21wZRzl8J5I2PtJF6XYe9ecbbPVJ/aHAG1QNGS1cHIHfVZRSzo3e4v+MJu7WyHqdpHCxFTh13ltDRE4bCcW0ZdALoJiwvp7FXM124PLwwDFDDxdws4RdDveoW4eN3e/aCDdjI5GUhVO8Xv9Y1pnUOm1OmeulFHYQZ+JL+CiEKgvbAfP908iVYK9g0sG8j3nvKVPKcQhGhM3PIdxTDcOH2H5SxyiWImEphoVxhVuU8ymduCIl9vK31wqxeepfPB6RZaUYtPHpxvahlSbNNri0q/aHq2uW/WW9BvRYssFN3U/wuSt6SsDH64UxYSP/Uamc1bBArorFZ+7p9wl9p74bc+vE2/aa+W/4SqS8PBWLPf2HQWAGQ2Vw9QlMsAKRxc1dffnCgivg+00x4meeARDEWlfxNWDC8YerG X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(61668805478150)(60795455431006)(190756311086443)(9452136761055)(1553240931313)(104084551191319)(228905959029699); X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(93006095)(93001095)(10201501046)(3231254)(944501410)(52105095)(3002001)(149027)(150027)(6041310)(20161123564045)(20161123558120)(20161123560045)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(6072148)(201708071742011)(7699016);SRVR:DM6PR05MB4585;BCL:0;PCL:0;RULEID:;SRVR:DM6PR05MB4585; X-Microsoft-Exchange-Diagnostics: 1;DM6PR05MB4585;4:jfv0drMWFqqxSLt3zEmato7x2oDBss7lAV71hEPOTJetLjU7WIMRjQKsixWqgbhYZB2c2JgjMqZ2mobmDdhXUCPifQe3gtoo5NhdXHMPWGj/iViWfVLO5NB3tGkdpxfLF+/bnpOe0d5GC4wvMPYKaSTwmz5KH8pwpNBG+B8FvgK7ztKtEs5r45w+H0FTkmT1cV9zV20Q5EAbfsFGyx0zs5SQUAbaQhR5+IFaEV/m1ueZX12I5TLTFJUhuGln/APW0h5ir+Dy6o9AMmakmIF3W5QF7ZLSEtn0sJBh7FUgS/FVFXLMw6hTv2rO8vmg/eiv/HzA6AgbahGU79+H1oELstosrhFqIpuZxNrUxeQp56uRWOyXGBT8ssm8UQ96wplDqEzZPdH044+wwMP+3+N+KXUrSSsmmHRPM1HWIqlex5lCHf6YZyRPXR6wwF4uyJ69lkmQNHXTUniuCZjedDdNDwWIh7mnzKMx+MKJaEttkvVUlRdOQjw3Sc0wpQJGRegFAn1ypjoY7P1xl/uXVvQlSQ== X-Forefront-PRVS: 07083FF734 X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10009020)(6069001)(39380400002)(346002)(396003)(39860400002)(376002)(366004)(199004)(189003)(106356001)(68736007)(76506005)(53416004)(956004)(105586002)(11346002)(7736002)(305945005)(6116002)(53936002)(316002)(54906003)(3846002)(69596002)(478600001)(486006)(50226002)(66066001)(2906002)(186003)(16526019)(575784001)(48376002)(47776003)(5660300001)(26005)(97736004)(6486002)(8676002)(7696005)(52116002)(86362001)(76176011)(51416003)(8936002)(476003)(2616005)(16586007)(25786009)(1076002)(59450400001)(446003)(4326008)(6666003)(81156014)(81166006)(7416002)(551934003)(36756003)(50466002)(386003);DIR:OUT;SFP:1101;SCL:1;SRVR:DM6PR05MB4585;H:localhost.vmware.com;FPR:;SPF:None;LANG:en;PTR:InfoNoRecords;A:1;MX:1; Received-SPF: None (protection.outlook.com: vmware.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1;DM6PR05MB4585;23:jf0BOH9Y3DUDRCp7DXBFXYO/rGMho4rA7NLaATd8U?= =?us-ascii?Q?PHHF6oWxT4fQlNXWmgnnnDBZ5Cu7IZO5vSz9lP1p2Tg9O8UcwZJReCOY22vF?= =?us-ascii?Q?dgE6kICv7qMcz20gcbqLe/DDHpFhho13iJA8f27e8hyrYL6sAAWIVz7RPcd0?= =?us-ascii?Q?rpxxtPzMeoncys5y1Nkkqoqtt2BzGZwPFu7jPIj0qWjMBY563Vw93zqHjSDh?= =?us-ascii?Q?fyTIVymHgbp2/DXDyfuF7FyH5efxu6vnXw3rcVJNJLZakdBOgyMewx9IKQ5d?= =?us-ascii?Q?PmGtUurjyXS4CTGf+u9BqXX8UdC3GGsh86ZEcwbd6M9VG4sW5Gyp2IIcxz0u?= =?us-ascii?Q?+Ake91rCZQYiKQFCjkkgA5wpxmFOtmvlLXeJjgFYLmIB9AZXpurE+iH3lKaw?= =?us-ascii?Q?DVQeSxRLPynHetNsb+QsaKYtA+pDANTMO8wj09i/vUsOCo7J06uxNXkf9sXD?= =?us-ascii?Q?h3uLNDT0NsDI6hsIUl1tt46Bz9I1ZIT4GZ34pfoJjLBed/7SQ92T4yfmKjSp?= =?us-ascii?Q?i8nEuAc1jrqrRJVUsa2nGNv9hdmy1YWsfE2LBByfeCfLPrbTiu4/ROqlPbU1?= =?us-ascii?Q?QBA5DozpH3bghpTzcFotrN71UKNaIYnrBzHp1EttBbZ5WvZ0434mNBgbcFjP?= =?us-ascii?Q?8nJBNGWqnVrKHTYPPm8MbkGM7q+Frfygtk5EKepkvAkNxcrskYCZDjV9q7oo?= =?us-ascii?Q?+Xm/CJelDWzflf+Gen1y7k8k76jB+oYJsD0Kx1N+fV6OzqlX8a7Bm1FRYA8X?= =?us-ascii?Q?Bl2rIysAzYWBOiwOyev8v9QV5igee8u7QXsbUJ5ZfEA2bEE7gVMOF9yUJP8E?= =?us-ascii?Q?6WTCnsW6tXvdNtADpujG7kiBCXseJomZPF7pnpgH5qAHIZ0J0yBIf/Kz6Y3y?= =?us-ascii?Q?YDWAPOy2DxohZG/bmASNeb8EZrrV97v6B9XZFU4JczL9kR/BDJU/Ubx0Cdvw?= =?us-ascii?Q?xYUUBZDeluSvjcNPA2fn28Q9IW66DMylc3dOt3e42Td4e+XoHcujpazRFAoR?= =?us-ascii?Q?pmXskbHuR0c711HGlg6wHe4eA9otNKL1sTeOXRY5vkvprRQxlXhPxNvL4DO5?= =?us-ascii?Q?w8W21bCsaCUcJchhoEb21osgv+UkeOTI0dJMJTmRZ/2izy7wcfkYP+FyBREL?= =?us-ascii?Q?HjkTO3rz/guPH7YCfJoy64rF69RkT46CZxZ4t5wde1trG2A3Cvgl9ymi+u3B?= =?us-ascii?Q?1/GEudl64CLyKZbFFszKdvQHHOgulzZQ5Ka+aC3sCy2UiKmPnoCWChHdg9o8?= =?us-ascii?Q?yQO4cTkl9FCMq+j1/o83aeNM35TaZz1DN+YaDR/+zNJg/eSAyHoPGivW8s96?= =?us-ascii?Q?zfEcUK/rgia3GkzrVRUjL3CWNvqLsXQTxHpmI1y4OJvzoRBF0EWxzhQBo49r?= =?us-ascii?Q?x+kDQ=3D=3D?= X-Microsoft-Antispam-Message-Info: 3CpJyyxsgXPOh3kTaAcO9/tm2Qav0+WLRa6sIML2huM0v2vpOFofxaNh+NYXw6quAgxO8iCpbzOpOXfeRJjCWgIPEQkDuBMgrhbW3IP9qC8ZYzOWgjIotzhlmwWnLklJx2sH45H+xuSRSrTiZmbAx3umcb+ehT22AZYmEQzZGWVH23Bx2uiA3hy6ZSdKSGmqDWjSfb2Dtm+87559a5C6GLiG3VqXy4hPDKKQ3ZExOaNZjP3GXpidyKRp+HKs/z1YyQ3GXbVfv0uUwCaWnABZBOZvfA3nFdvKq786fWctuP4LkJ49Ifs8SK9JsMtTcYRB+zQmwISq3+xr0MLkqRe0Ew== X-Microsoft-Exchange-Diagnostics: 1;DM6PR05MB4585;6:LwzAkvRSS7NRnJxkZzP6huHs8DzmVOBiYfftO5uOECAgKjmE9i7hagY2WZGwWBtvnleO4vWCvwWmGsnx564AA3k7+FSAN4ZedJU9RwKUfA5E3DR7l1XtDx+PIO65XYCLGLixSgC6bGu5xSQYPC6ha7IzTKL07FyorhxEqcFSANe9/7c81iB1xqMiQ8gyhMnz6jHIUTohcXA9IZw0TZGIqafMrWi0NggVpQsnUzb4c2Lipax9kGNc4PvyUx5WBnB4cwy5GOBhIgOyfAlHiwfKlqfuDtNg8To2d5TPZEqcn1bbo8bymW3elXMWGF0We9AVrp3w7Educ0xc9wtP9rTqTIUjHReIOIlWt9YS2/kVO/vD81xgxNN6M0HhF5Pn54Ppihuaap2vBqUPYKUo7Rgrb33ZMqk7mmj11suC7t6TkOYcYH/HlpdfM3f9tsWerDuQWGnJuiBcgUzDkJrPjA9dKA==;5:zm1WEBm74/OKiqnWsnlVIRRs+qhEeYbKE2lk4Yc4hxVL+JwsU6eRz48nd3uMqU0ueZkmJEC7y3DuMa8gIb7NzojlAXwUjsTQMBha4+Bq9/2xUOVgQ4JWRyg2X8PlYSb1FYQFRZNjbEQa4C/MmkgbWzPkmB1yHLYEDowvyjByY2E=;24:rySwf7Rg+40RtoX4OH4pJxrzgjVB7IFHhMpaJjuHEoWpYhyTFV6M1VsOJs2gVdw7SQqpCkeAdckA8Oy6ngmDSEb93z6JeWg5026C3sK2CWo= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;DM6PR05MB4585;7:6ssv07h6BH4HVEZMKAK9+0IgB0digGXpbMKvSOsFSRMWfxSxRBgEFt60eIUc1jG+eUQn3cZQDDUFvwoprC9zrUMoJBNRlXmeM7xzutjC3HErIbVgKiaXOhEN0bhhuXFSHuxhjkIkSXb4ZqZhI2BdKUdaECMa8BYd8vAbRFC7aSHhd/MoQ24dV1o2EQ+PoJO0dtML4UCXsc5/+/dW8KnWePhgV1Ix6I/12scEkxEvJchD/HGfv5z8LPpdzvSTNrSg;20:CoMFxNOhV8nGqBktWz+ss3ZiLkRCZVoZKPe4LjFd98OFn32yb+ALnnWUryMFrkcEJA/g66+WOyfDCPlUctNRIqiGsR4jarDiuSZc7UhLjzUAfXoSU0JDjSMgkRjsuU0MXX4zZXm7Vfa9ySxLiLeXKkphU0xwXFUIH52qEHRC7sk= X-OriginatorOrg: vmware.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 19 Jun 2018 08:25:53.7903 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: e0a09575-28bd-496c-cbc5-08d5d5be490a X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: b39138ca-3cee-4b4a-a4d6-cd83d9dd62f0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR05MB4585 Sender: linux-doc-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-doc@vger.kernel.org The current Wound-Wait mutex algorithm is actually not Wound-Wait but Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait is, contrary to Wait-Die a preemptive algorithm and is known to generate fewer backoffs. Testing reveals that this is true if the number of simultaneous contending transactions is small. As the number of simultaneous contending threads increases, Wait-Wound becomes inferior to Wait-Die in terms of elapsed time. Possibly due to the larger number of held locks of sleeping transactions. Update documentation and callers. Timings using git://people.freedesktop.org/~thomash/ww_mutex_test tag patch-18-06-15 Each thread runs 100000 batches of lock / unlock 800 ww mutexes randomly chosen out of 100000. Four core Intel x86_64: Algorithm #threads Rollbacks time Wound-Wait 4 ~100 ~17s. Wait-Die 4 ~150000 ~19s. Wound-Wait 16 ~360000 ~109s. Wait-Die 16 ~450000 ~82s. Cc: Ingo Molnar Cc: Jonathan Corbet Cc: Gustavo Padovan Cc: Maarten Lankhorst Cc: Sean Paul Cc: David Airlie Cc: Davidlohr Bueso Cc: "Paul E. McKenney" Cc: Josh Triplett Cc: Thomas Gleixner Cc: Kate Stewart Cc: Philippe Ombredanne Cc: Greg Kroah-Hartman Cc: linux-doc@vger.kernel.org Cc: linux-media@vger.kernel.org Cc: linaro-mm-sig@lists.linaro.org Co-authored-by: Peter Zijlstra Signed-off-by: Thomas Hellstrom --- v2: * Update API according to review comment by Greg Kroah-Hartman. * Address review comments by Peter Zijlstra: - Avoid _Bool in composites - Fix typo - Use __mutex_owner() where applicable - Rely on built-in barriers for the main loop exit condition, struct ww_acquire_ctx::wounded. Update code comments. - Explain unlocked use of list_empty(). v3: * Adapt to and incorporate cleanup by Peter Zijlstra * Remove unlocked use of list_empty(). v4: * Move code related to adding a waiter to the lock waiter list to a separate function. --- Documentation/locking/ww-mutex-design.txt | 57 +++++++++-- drivers/dma-buf/reservation.c | 2 +- drivers/gpu/drm/drm_modeset_lock.c | 2 +- include/linux/ww_mutex.h | 17 ++- kernel/locking/locktorture.c | 2 +- kernel/locking/mutex.c | 165 +++++++++++++++++++++++++++--- kernel/locking/test-ww_mutex.c | 2 +- lib/locking-selftest.c | 2 +- 8 files changed, 213 insertions(+), 36 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 2fd7f2a2af21..f0ed7c30e695 100644 --- a/Documentation/locking/ww-mutex-design.txt +++ b/Documentation/locking/ww-mutex-design.txt @@ -1,4 +1,4 @@ -Wait/Wound Deadlock-Proof Mutex Design +Wound/Wait Deadlock-Proof Mutex Design ====================================== Please read mutex-design.txt first, as it applies to wait/wound mutexes too. @@ -32,10 +32,26 @@ the oldest task) wins, and the one with the higher reservation id (i.e. the younger task) unlocks all of the buffers that it has already locked, and then tries again. -In the RDBMS literature this deadlock handling approach is called wait/die: -The older tasks waits until it can acquire the contended lock. The younger tasks -needs to back off and drop all the locks it is currently holding, i.e. the -younger task dies. +In the RDBMS literature, a reservation ticket is associated with a transaction. +and the deadlock handling approach is called Wait-Die. The name is based on +the actions of a locking thread when it encounters an already locked mutex. +If the transaction holding the lock is younger, the locking transaction waits. +If the transaction holding the lock is older, the locking transaction backs off +and dies. Hence Wait-Die. +There is also another algorithm called Wound-Wait: +If the transaction holding the lock is younger, the locking transaction +wounds the transaction holding the lock, requesting it to die. +If the transaction holding the lock is older, it waits for the other +transaction. Hence Wound-Wait. +The two algorithms are both fair in that a transaction will eventually succeed. +However, the Wound-Wait algorithm is typically stated to generate fewer backoffs +compared to Wait-Die, but is, on the other hand, associated with more work than +Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive +algorithm in that transactions are wounded by other transactions, and that +requires a reliable way to pick up up the wounded condition and preempt the +running transaction. Note that this is not the same as process preemption. A +Wound-Wait transaction is considered preempted when it dies (returning +-EDEADLK) following a wound. Concepts -------- @@ -47,10 +63,12 @@ Acquire context: To ensure eventual forward progress it is important the a task trying to acquire locks doesn't grab a new reservation id, but keeps the one it acquired when starting the lock acquisition. This ticket is stored in the acquire context. Furthermore the acquire context keeps track of debugging state -to catch w/w mutex interface abuse. +to catch w/w mutex interface abuse. An acquire context is representing a +transaction. W/w class: In contrast to normal mutexes the lock class needs to be explicit for -w/w mutexes, since it is required to initialize the acquire context. +w/w mutexes, since it is required to initialize the acquire context. The lock +class also specifies what algorithm to use, Wound-Wait or Wait-Die. Furthermore there are three different class of w/w lock acquire functions: @@ -90,6 +108,12 @@ provided. Usage ----- +The algorithm (Wait-Die vs Wound-Wait) is chosen by using either +DEFINE_WW_CLASS() (Wound-Wait) or DEFINE_WD_CLASS() (Wait-Die) +As a rough rule of thumb, use Wound-Wait iff you +expect the number of simultaneous competing transactions to be typically small, +and you want to reduce the number of rollbacks. + Three different ways to acquire locks within the same w/w class. Common definitions for methods #1 and #2: @@ -312,12 +336,23 @@ Design: We maintain the following invariants for the wait list: (1) Waiters with an acquire context are sorted by stamp order; waiters without an acquire context are interspersed in FIFO order. - (2) Among waiters with contexts, only the first one can have other locks - acquired already (ctx->acquired > 0). Note that this waiter may come - after other waiters without contexts in the list. + (2) For Wait-Die, among waiters with contexts, only the first one can have + other locks acquired already (ctx->acquired > 0). Note that this waiter + may come after other waiters without contexts in the list. + + The Wound-Wait preemption is implemented with a lazy-preemption scheme: + The wounded status of the transaction is checked only when there is + contention for a new lock and hence a true chance of deadlock. In that + situation, if the transaction is wounded, it backs off, clears the + wounded status and retries. A great benefit of implementing preemption in + this way is that the wounded transaction can identify a contending lock to + wait for before restarting the transaction. Just blindly restarting the + transaction would likely make the transaction end up in a situation where + it would have to back off again. In general, not much contention is expected. The locks are typically used to - serialize access to resources for devices. + serialize access to resources for devices, and optimization focus should + therefore be directed towards the uncontended cases. Lockdep: Special care has been taken to warn for as many cases of api abuse diff --git a/drivers/dma-buf/reservation.c b/drivers/dma-buf/reservation.c index 314eb1071cce..20bf90f4ee63 100644 --- a/drivers/dma-buf/reservation.c +++ b/drivers/dma-buf/reservation.c @@ -46,7 +46,7 @@ * write-side updates. */ -DEFINE_WW_CLASS(reservation_ww_class); +DEFINE_WD_CLASS(reservation_ww_class); EXPORT_SYMBOL(reservation_ww_class); struct lock_class_key reservation_seqcount_class; diff --git a/drivers/gpu/drm/drm_modeset_lock.c b/drivers/gpu/drm/drm_modeset_lock.c index 8a5100685875..638be2eb67b4 100644 --- a/drivers/gpu/drm/drm_modeset_lock.c +++ b/drivers/gpu/drm/drm_modeset_lock.c @@ -70,7 +70,7 @@ * lists and lookup data structures. */ -static DEFINE_WW_CLASS(crtc_ww_class); +static DEFINE_WD_CLASS(crtc_ww_class); /** * drm_modeset_lock_all - take all modeset locks diff --git a/include/linux/ww_mutex.h b/include/linux/ww_mutex.h index f82fce2229c8..3af7c0e03be5 100644 --- a/include/linux/ww_mutex.h +++ b/include/linux/ww_mutex.h @@ -8,6 +8,8 @@ * * Wait/Die implementation: * Copyright (C) 2013 Canonical Ltd. + * Choice of algorithm: + * Copyright (C) 2018 WMWare Inc. * * This file contains the main data structure and API definitions. */ @@ -23,12 +25,15 @@ struct ww_class { struct lock_class_key mutex_key; const char *acquire_name; const char *mutex_name; + unsigned int is_wait_die; }; struct ww_acquire_ctx { struct task_struct *task; unsigned long stamp; unsigned int acquired; + unsigned short wounded; + unsigned short is_wait_die; #ifdef CONFIG_DEBUG_MUTEXES unsigned int done_acquire; struct ww_class *ww_class; @@ -58,17 +63,21 @@ struct ww_mutex { # define __WW_CLASS_MUTEX_INITIALIZER(lockname, class) #endif -#define __WW_CLASS_INITIALIZER(ww_class) \ +#define __WW_CLASS_INITIALIZER(ww_class, _is_wait_die) \ { .stamp = ATOMIC_LONG_INIT(0) \ , .acquire_name = #ww_class "_acquire" \ - , .mutex_name = #ww_class "_mutex" } + , .mutex_name = #ww_class "_mutex" \ + , .is_wait_die = _is_wait_die } #define __WW_MUTEX_INITIALIZER(lockname, class) \ { .base = __MUTEX_INITIALIZER(lockname.base) \ __WW_CLASS_MUTEX_INITIALIZER(lockname, class) } +#define DEFINE_WD_CLASS(classname) \ + struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 1) + #define DEFINE_WW_CLASS(classname) \ - struct ww_class classname = __WW_CLASS_INITIALIZER(classname) + struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 0) #define DEFINE_WW_MUTEX(mutexname, ww_class) \ struct ww_mutex mutexname = __WW_MUTEX_INITIALIZER(mutexname, ww_class) @@ -123,6 +132,8 @@ static inline void ww_acquire_init(struct ww_acquire_ctx *ctx, ctx->task = current; ctx->stamp = atomic_long_inc_return_relaxed(&ww_class->stamp); ctx->acquired = 0; + ctx->wounded = false; + ctx->is_wait_die = ww_class->is_wait_die; #ifdef CONFIG_DEBUG_MUTEXES ctx->ww_class = ww_class; ctx->done_acquire = 0; diff --git a/kernel/locking/locktorture.c b/kernel/locking/locktorture.c index 6850ffd69125..907e0325892c 100644 --- a/kernel/locking/locktorture.c +++ b/kernel/locking/locktorture.c @@ -365,7 +365,7 @@ static struct lock_torture_ops mutex_lock_ops = { }; #include -static DEFINE_WW_CLASS(torture_ww_class); +static DEFINE_WD_CLASS(torture_ww_class); static DEFINE_WW_MUTEX(torture_ww_mutex_0, &torture_ww_class); static DEFINE_WW_MUTEX(torture_ww_mutex_1, &torture_ww_class); static DEFINE_WW_MUTEX(torture_ww_mutex_2, &torture_ww_class); diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 412b4fc08235..8ca83a5e3d24 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -172,6 +172,21 @@ static inline bool __mutex_waiter_is_first(struct mutex *lock, struct mutex_wait return list_first_entry(&lock->wait_list, struct mutex_waiter, list) == waiter; } +/* + * Add @waiter to a given location in the lock wait_list and set the + * FLAG_WAITERS flag if it's the first waiter. + */ +static void __sched +__mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter, + struct list_head *list) +{ + debug_mutex_add_waiter(lock, waiter, current); + + list_add_tail(&waiter->list, list); + if (__mutex_waiter_is_first(lock, waiter)) + __mutex_set_flag(lock, MUTEX_FLAG_WAITERS); +} + /* * Give up ownership to a specific task, when @task = NULL, this is equivalent * to a regular unlock. Sets PICKUP on a handoff, clears HANDOF, preserves @@ -248,6 +263,11 @@ EXPORT_SYMBOL(mutex_lock); * The newer transactions are killed when: * It (the new transaction) makes a request for a lock being held * by an older transaction. + * + * Wound-Wait: + * The newer transactions are wounded when: + * An older transaction makes a request for a lock being held by + * the newer transaction. */ /* @@ -319,6 +339,9 @@ static bool __sched __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter, struct ww_acquire_ctx *ww_ctx) { + if (!ww_ctx->is_wait_die) + return false; + if (waiter->ww_ctx->acquired > 0 && __ww_ctx_stamp_after(waiter->ww_ctx, ww_ctx)) { debug_mutex_wake_waiter(lock, waiter); @@ -328,13 +351,65 @@ __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter, return true; } +/* + * Wound-Wait; wound a younger @hold_ctx if it holds the lock. + * + * Wound the lock holder if there are waiters with older transactions than + * the lock holders. Even if multiple waiters may wound the lock holder, + * it's sufficient that only one does. + */ +static bool __ww_mutex_wound(struct mutex *lock, + struct ww_acquire_ctx *ww_ctx, + struct ww_acquire_ctx *hold_ctx) +{ + struct task_struct *owner = __mutex_owner(lock); + + lockdep_assert_held(&lock->wait_lock); + + /* + * Possible through __ww_mutex_add_waiter() when we race with + * ww_mutex_set_context_fastpath(). In that case we'll get here again + * through __ww_mutex_check_waiters(). + */ + if (!hold_ctx) + return false; + + /* + * Can have !owner because of __mutex_unlock_slowpath(), but if owner, + * it cannot go away because we'll have FLAG_WAITERS set and hold + * wait_lock. + */ + if (!owner) + return false; + + if (ww_ctx->acquired > 0 && __ww_ctx_stamp_after(hold_ctx, ww_ctx)) { + hold_ctx->wounded = 1; + + /* + * wake_up_process() paired with set_current_state() + * inserts sufficient barriers to make sure @owner either sees + * it's wounded in __ww_mutex_lock_check_stamp() or has a + * wakeup pending to re-read the wounded state. + */ + if (owner != current) + wake_up_process(owner); + + return true; + } + + return false; +} + /* * We just acquired @lock under @ww_ctx, if there are later contexts waiting - * behind us on the wait-list, check if they need to die. + * behind us on the wait-list, check if they need to die, or wound us. * * See __ww_mutex_add_waiter() for the list-order construction; basically the * list is ordered by stamp, smallest (oldest) first. * + * This relies on never mixing wait-die/wound-wait on the same wait-list; + * which is currently ensured by that being a ww_class property. + * * The current task must not be on the wait list. */ static void __sched @@ -348,7 +423,8 @@ __ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) if (!cur->ww_ctx) continue; - if (__ww_mutex_die(lock, cur, ww_ctx)) + if (__ww_mutex_die(lock, cur, ww_ctx) || + __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx)) break; } } @@ -369,17 +445,23 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) * and keep spinning, or it will acquire wait_lock, add itself * to waiter list and sleep. */ - smp_mb(); /* ^^^ */ + smp_mb(); /* See comments above and below. */ /* - * Check if lock is contended, if not there is nobody to wake up + * [W] ww->ctx = ctx [W] MUTEX_FLAG_WAITERS + * MB MB + * [R] MUTEX_FLAG_WAITERS [R] ww->ctx + * + * The memory barrier above pairs with the memory barrier in + * __ww_mutex_add_waiter() and makes sure we either observe ww->ctx + * and/or !empty list. */ if (likely(!(atomic_long_read(&lock->base.owner) & MUTEX_FLAG_WAITERS))) return; /* * Uh oh, we raced in fastpath, check if any of the waiters need to - * die. + * die or wound us. */ spin_lock(&lock->base.wait_lock); __ww_mutex_check_waiters(&lock->base, ctx); @@ -681,7 +763,9 @@ __ww_mutex_kill(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) /* - * Check whether we need to kill the transaction for the current lock acquire. + * Check the wound condition for the current lock acquire. + * + * Wound-Wait: If we're wounded, kill ourself. * * Wait-Die: If we're trying to acquire a lock already held by an older * context, kill ourselves. @@ -700,6 +784,13 @@ __ww_mutex_check_kill(struct mutex *lock, struct mutex_waiter *waiter, if (ctx->acquired == 0) return 0; + if (!ctx->is_wait_die) { + if (ctx->wounded) + return __ww_mutex_kill(lock, ctx); + + return 0; + } + if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx)) return __ww_mutex_kill(lock, ctx); @@ -726,7 +817,8 @@ __ww_mutex_check_kill(struct mutex *lock, struct mutex_waiter *waiter, * Waiters without context are interspersed in FIFO order. * * Furthermore, for Wait-Die kill ourself immediately when possible (there are - * older contexts already waiting) to avoid unnecessary waiting. + * older contexts already waiting) to avoid unnecessary waiting and for + * Wound-Wait ensure we wound the owning context when it is younger. */ static inline int __sched __ww_mutex_add_waiter(struct mutex_waiter *waiter, @@ -735,16 +827,21 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, { struct mutex_waiter *cur; struct list_head *pos; + bool is_wait_die; if (!ww_ctx) { - list_add_tail(&waiter->list, &lock->wait_list); + __mutex_add_waiter(lock, waiter, &lock->wait_list); return 0; } + is_wait_die = ww_ctx->is_wait_die; + /* * Add the waiter before the first waiter with a higher stamp. * Waiters without a context are skipped to avoid starving - * them. Wait-Die waiters may die here. + * them. Wait-Die waiters may die here. Wound-Wait waiters + * never die here, but they are sorted in stamp order and + * may wound the lock holder. */ pos = &lock->wait_list; list_for_each_entry_reverse(cur, &lock->wait_list, list) { @@ -757,10 +854,12 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, * is no point in queueing behind it, as we'd have to * die the moment it would acquire the lock. */ - int ret = __ww_mutex_kill(lock, ww_ctx); + if (is_wait_die) { + int ret = __ww_mutex_kill(lock, ww_ctx); - if (ret) - return ret; + if (ret) + return ret; + } break; } @@ -771,7 +870,23 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, __ww_mutex_die(lock, cur, ww_ctx); } - list_add_tail(&waiter->list, pos); + __mutex_add_waiter(lock, waiter, pos); + + /* + * Wound-Wait: if we're blocking on a mutex owned by a younger context, + * wound that such that we might proceed. + */ + if (!is_wait_die) { + struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); + + /* + * See ww_mutex_set_context_fastpath(). Orders setting + * MUTEX_FLAG_WAITERS vs the ww->ctx load, + * such that either we or the fastpath will wound @ww->ctx. + */ + smp_mb(); + __ww_mutex_wound(lock, ww_ctx, ww->ctx); + } return 0; } @@ -795,6 +910,14 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, if (use_ww_ctx && ww_ctx) { if (unlikely(ww_ctx == READ_ONCE(ww->ctx))) return -EALREADY; + + /* + * Reset the wounded flag after a kill. No other process can + * race and wound us here since they can't have a valid owner + * pointer if we don't have any locks held. + */ + if (ww_ctx->acquired == 0) + ww_ctx->wounded = 0; } preempt_disable(); @@ -828,7 +951,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, if (!use_ww_ctx) { /* add waiting tasks to the end of the waitqueue (FIFO): */ - list_add_tail(&waiter.list, &lock->wait_list); + __mutex_add_waiter(lock, &waiter, &lock->wait_list); + #ifdef CONFIG_DEBUG_MUTEXES waiter.ww_ctx = MUTEX_POISON_WW_CTX; @@ -847,9 +971,6 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, waiter.task = current; - if (__mutex_waiter_is_first(lock, &waiter)) - __mutex_set_flag(lock, MUTEX_FLAG_WAITERS); - set_current_state(state); for (;;) { /* @@ -906,6 +1027,16 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, acquired: __set_current_state(TASK_RUNNING); + if (use_ww_ctx && ww_ctx) { + /* + * Wound-Wait; we stole the lock (!first_waiter), check the + * waiters as anyone might want to wound us. + */ + if (!ww_ctx->is_wait_die && + !__mutex_waiter_is_first(lock, &waiter)) + __ww_mutex_check_waiters(lock, ww_ctx); + } + mutex_remove_waiter(lock, &waiter, current); if (likely(list_empty(&lock->wait_list))) __mutex_clear_flag(lock, MUTEX_FLAGS); diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c index 0e4cd64ad2c0..5b915b370d5a 100644 --- a/kernel/locking/test-ww_mutex.c +++ b/kernel/locking/test-ww_mutex.c @@ -26,7 +26,7 @@ #include #include -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WD_CLASS(ww_class); struct workqueue_struct *wq; struct test_mutex { diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index b5c1293ce147..1e1bbf171eca 100644 --- a/lib/locking-selftest.c +++ b/lib/locking-selftest.c @@ -29,7 +29,7 @@ */ static unsigned int debug_locks_verbose; -static DEFINE_WW_CLASS(ww_lockdep); +static DEFINE_WD_CLASS(ww_lockdep); static int __init setup_debug_locks_verbose(char *str) { -- 2.14.3 -- To unsubscribe from this list: send the line "unsubscribe linux-doc" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html From mboxrd@z Thu Jan 1 00:00:00 1970 From: Thomas Hellstrom Subject: [PATCH v4 2/3] locking: Implement an algorithm choice for Wound-Wait mutexes Date: Tue, 19 Jun 2018 10:24:44 +0200 Message-ID: <20180619082445.11062-3-thellstrom@vmware.com> References: <20180619082445.11062-1-thellstrom@vmware.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: Received: from NAM05-DM3-obe.outbound.protection.outlook.com (mail-dm3nam05on0619.outbound.protection.outlook.com [IPv6:2a01:111:f400:fe51::619]) by gabe.freedesktop.org (Postfix) with ESMTPS id CA2B06E4C0 for ; Tue, 19 Jun 2018 08:26:05 +0000 (UTC) In-Reply-To: <20180619082445.11062-1-thellstrom@vmware.com> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" To: dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, peterz@infradead.org Cc: Kate Stewart , Thomas Hellstrom , Davidlohr Bueso , Jonathan Corbet , pv-drivers@vmware.com, linux-doc@vger.kernel.org, Josh Triplett , linaro-mm-sig@lists.linaro.org, David Airlie , Greg Kroah-Hartman , Ingo Molnar , linux-graphics-maintainer@vmware.com, Philippe Ombredanne , Thomas Gleixner , "Paul E. McKenney" , linux-media@vger.kernel.org List-Id: dri-devel@lists.freedesktop.org VGhlIGN1cnJlbnQgV291bmQtV2FpdCBtdXRleCBhbGdvcml0aG0gaXMgYWN0dWFsbHkgbm90IFdv dW5kLVdhaXQgYnV0CldhaXQtRGllLiBJbXBsZW1lbnQgYWxzbyBXb3VuZC1XYWl0IGFzIGEgcGVy LXd3LWNsYXNzIGNob2ljZS4gV291bmQtV2FpdAppcywgY29udHJhcnkgdG8gV2FpdC1EaWUgYSBw cmVlbXB0aXZlIGFsZ29yaXRobSBhbmQgaXMga25vd24gdG8gZ2VuZXJhdGUKZmV3ZXIgYmFja29m ZnMuIFRlc3RpbmcgcmV2ZWFscyB0aGF0IHRoaXMgaXMgdHJ1ZSBpZiB0aGUKbnVtYmVyIG9mIHNp bXVsdGFuZW91cyBjb250ZW5kaW5nIHRyYW5zYWN0aW9ucyBpcyBzbWFsbC4KQXMgdGhlIG51bWJl ciBvZiBzaW11bHRhbmVvdXMgY29udGVuZGluZyB0aHJlYWRzIGluY3JlYXNlcywgV2FpdC1Xb3Vu ZApiZWNvbWVzIGluZmVyaW9yIHRvIFdhaXQtRGllIGluIHRlcm1zIG9mIGVsYXBzZWQgdGltZS4K UG9zc2libHkgZHVlIHRvIHRoZSBsYXJnZXIgbnVtYmVyIG9mIGhlbGQgbG9ja3Mgb2Ygc2xlZXBp bmcgdHJhbnNhY3Rpb25zLgoKVXBkYXRlIGRvY3VtZW50YXRpb24gYW5kIGNhbGxlcnMuCgpUaW1p bmdzIHVzaW5nIGdpdDovL3Blb3BsZS5mcmVlZGVza3RvcC5vcmcvfnRob21hc2gvd3dfbXV0ZXhf dGVzdAp0YWcgcGF0Y2gtMTgtMDYtMTUKCkVhY2ggdGhyZWFkIHJ1bnMgMTAwMDAwIGJhdGNoZXMg b2YgbG9jayAvIHVubG9jayA4MDAgd3cgbXV0ZXhlcyByYW5kb21seQpjaG9zZW4gb3V0IG9mIDEw MDAwMC4gRm91ciBjb3JlIEludGVsIHg4Nl82NDoKCkFsZ29yaXRobSAgICAjdGhyZWFkcyAgICAg ICBSb2xsYmFja3MgIHRpbWUKV291bmQtV2FpdCAgIDQgICAgICAgICAgICAgIH4xMDAgICAgICAg fjE3cy4KV2FpdC1EaWUgICAgIDQgICAgICAgICAgICAgIH4xNTAwMDAgICAgfjE5cy4KV291bmQt V2FpdCAgIDE2ICAgICAgICAgICAgIH4zNjAwMDAgICAgfjEwOXMuCldhaXQtRGllICAgICAxNiAg ICAgICAgICAgICB+NDUwMDAwICAgIH44MnMuCgpDYzogSW5nbyBNb2xuYXIgPG1pbmdvQHJlZGhh dC5jb20+CkNjOiBKb25hdGhhbiBDb3JiZXQgPGNvcmJldEBsd24ubmV0PgpDYzogR3VzdGF2byBQ YWRvdmFuIDxndXN0YXZvQHBhZG92YW4ub3JnPgpDYzogTWFhcnRlbiBMYW5raG9yc3QgPG1hYXJ0 ZW4ubGFua2hvcnN0QGxpbnV4LmludGVsLmNvbT4KQ2M6IFNlYW4gUGF1bCA8c2VhbnBhdWxAY2hy b21pdW0ub3JnPgpDYzogRGF2aWQgQWlybGllIDxhaXJsaWVkQGxpbnV4LmllPgpDYzogRGF2aWRs b2hyIEJ1ZXNvIDxkYXZlQHN0Z29sYWJzLm5ldD4KQ2M6ICJQYXVsIEUuIE1jS2VubmV5IiA8cGF1 bG1ja0BsaW51eC52bmV0LmlibS5jb20+CkNjOiBKb3NoIFRyaXBsZXR0IDxqb3NoQGpvc2h0cmlw bGV0dC5vcmc+CkNjOiBUaG9tYXMgR2xlaXhuZXIgPHRnbHhAbGludXRyb25peC5kZT4KQ2M6IEth dGUgU3Rld2FydCA8a3N0ZXdhcnRAbGludXhmb3VuZGF0aW9uLm9yZz4KQ2M6IFBoaWxpcHBlIE9t YnJlZGFubmUgPHBvbWJyZWRhbm5lQG5leGIuY29tPgpDYzogR3JlZyBLcm9haC1IYXJ0bWFuIDxn cmVna2hAbGludXhmb3VuZGF0aW9uLm9yZz4KQ2M6IGxpbnV4LWRvY0B2Z2VyLmtlcm5lbC5vcmcK Q2M6IGxpbnV4LW1lZGlhQHZnZXIua2VybmVsLm9yZwpDYzogbGluYXJvLW1tLXNpZ0BsaXN0cy5s aW5hcm8ub3JnCkNvLWF1dGhvcmVkLWJ5OiBQZXRlciBaaWpsc3RyYSA8cGV0ZXJ6QGluZnJhZGVh ZC5vcmc+ClNpZ25lZC1vZmYtYnk6IFRob21hcyBIZWxsc3Ryb20gPHRoZWxsc3Ryb21Adm13YXJl LmNvbT4KCi0tLQp2MjoKKiBVcGRhdGUgQVBJIGFjY29yZGluZyB0byByZXZpZXcgY29tbWVudCBi eSBHcmVnIEtyb2FoLUhhcnRtYW4uCiogQWRkcmVzcyByZXZpZXcgY29tbWVudHMgYnkgUGV0ZXIg WmlqbHN0cmE6CiAgLSBBdm9pZCBfQm9vbCBpbiBjb21wb3NpdGVzCiAgLSBGaXggdHlwbwogIC0g VXNlIF9fbXV0ZXhfb3duZXIoKSB3aGVyZSBhcHBsaWNhYmxlCiAgLSBSZWx5IG9uIGJ1aWx0LWlu IGJhcnJpZXJzIGZvciB0aGUgbWFpbiBsb29wIGV4aXQgY29uZGl0aW9uLAogICAgc3RydWN0IHd3 X2FjcXVpcmVfY3R4Ojp3b3VuZGVkLiBVcGRhdGUgY29kZSBjb21tZW50cy4KICAtIEV4cGxhaW4g dW5sb2NrZWQgdXNlIG9mIGxpc3RfZW1wdHkoKS4KdjM6CiogQWRhcHQgdG8gYW5kIGluY29ycG9y YXRlIGNsZWFudXAgYnkgUGV0ZXIgWmlqbHN0cmEKKiBSZW1vdmUgdW5sb2NrZWQgdXNlIG9mIGxp c3RfZW1wdHkoKS4KdjQ6CiogTW92ZSBjb2RlIHJlbGF0ZWQgdG8gYWRkaW5nIGEgd2FpdGVyIHRv IHRoZSBsb2NrIHdhaXRlciBsaXN0IHRvIGEKICBzZXBhcmF0ZSBmdW5jdGlvbi4KLS0tCiBEb2N1 bWVudGF0aW9uL2xvY2tpbmcvd3ctbXV0ZXgtZGVzaWduLnR4dCB8ICA1NyArKysrKysrKystLQog ZHJpdmVycy9kbWEtYnVmL3Jlc2VydmF0aW9uLmMgICAgICAgICAgICAgfCAgIDIgKy0KIGRyaXZl cnMvZ3B1L2RybS9kcm1fbW9kZXNldF9sb2NrLmMgICAgICAgIHwgICAyICstCiBpbmNsdWRlL2xp bnV4L3d3X211dGV4LmggICAgICAgICAgICAgICAgICB8ICAxNyArKy0KIGtlcm5lbC9sb2NraW5n L2xvY2t0b3J0dXJlLmMgICAgICAgICAgICAgIHwgICAyICstCiBrZXJuZWwvbG9ja2luZy9tdXRl eC5jICAgICAgICAgICAgICAgICAgICB8IDE2NSArKysrKysrKysrKysrKysrKysrKysrKysrKyst LS0KIGtlcm5lbC9sb2NraW5nL3Rlc3Qtd3dfbXV0ZXguYyAgICAgICAgICAgIHwgICAyICstCiBs aWIvbG9ja2luZy1zZWxmdGVzdC5jICAgICAgICAgICAgICAgICAgICB8ICAgMiArLQogOCBmaWxl cyBjaGFuZ2VkLCAyMTMgaW5zZXJ0aW9ucygrKSwgMzYgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0 IGEvRG9jdW1lbnRhdGlvbi9sb2NraW5nL3d3LW11dGV4LWRlc2lnbi50eHQgYi9Eb2N1bWVudGF0 aW9uL2xvY2tpbmcvd3ctbXV0ZXgtZGVzaWduLnR4dAppbmRleCAyZmQ3ZjJhMmFmMjEuLmYwZWQ3 YzMwZTY5NSAxMDA2NDQKLS0tIGEvRG9jdW1lbnRhdGlvbi9sb2NraW5nL3d3LW11dGV4LWRlc2ln bi50eHQKKysrIGIvRG9jdW1lbnRhdGlvbi9sb2NraW5nL3d3LW11dGV4LWRlc2lnbi50eHQKQEAg LTEsNCArMSw0IEBACi1XYWl0L1dvdW5kIERlYWRsb2NrLVByb29mIE11dGV4IERlc2lnbgorV291 bmQvV2FpdCBEZWFkbG9jay1Qcm9vZiBNdXRleCBEZXNpZ24KID09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09CiAKIFBsZWFzZSByZWFkIG11dGV4LWRlc2lnbi50eHQgZmlyc3Qs IGFzIGl0IGFwcGxpZXMgdG8gd2FpdC93b3VuZCBtdXRleGVzIHRvby4KQEAgLTMyLDEwICszMiwy NiBAQCB0aGUgb2xkZXN0IHRhc2spIHdpbnMsIGFuZCB0aGUgb25lIHdpdGggdGhlIGhpZ2hlciBy ZXNlcnZhdGlvbiBpZCAoaS5lLiB0aGUKIHlvdW5nZXIgdGFzaykgdW5sb2NrcyBhbGwgb2YgdGhl IGJ1ZmZlcnMgdGhhdCBpdCBoYXMgYWxyZWFkeSBsb2NrZWQsIGFuZCB0aGVuCiB0cmllcyBhZ2Fp bi4KIAotSW4gdGhlIFJEQk1TIGxpdGVyYXR1cmUgdGhpcyBkZWFkbG9jayBoYW5kbGluZyBhcHBy b2FjaCBpcyBjYWxsZWQgd2FpdC9kaWU6Ci1UaGUgb2xkZXIgdGFza3Mgd2FpdHMgdW50aWwgaXQg Y2FuIGFjcXVpcmUgdGhlIGNvbnRlbmRlZCBsb2NrLiBUaGUgeW91bmdlciB0YXNrcwotbmVlZHMg dG8gYmFjayBvZmYgYW5kIGRyb3AgYWxsIHRoZSBsb2NrcyBpdCBpcyBjdXJyZW50bHkgaG9sZGlu ZywgaS5lLiB0aGUKLXlvdW5nZXIgdGFzayBkaWVzLgorSW4gdGhlIFJEQk1TIGxpdGVyYXR1cmUs IGEgcmVzZXJ2YXRpb24gdGlja2V0IGlzIGFzc29jaWF0ZWQgd2l0aCBhIHRyYW5zYWN0aW9uLgor YW5kIHRoZSBkZWFkbG9jayBoYW5kbGluZyBhcHByb2FjaCBpcyBjYWxsZWQgV2FpdC1EaWUuIFRo ZSBuYW1lIGlzIGJhc2VkIG9uCit0aGUgYWN0aW9ucyBvZiBhIGxvY2tpbmcgdGhyZWFkIHdoZW4g aXQgZW5jb3VudGVycyBhbiBhbHJlYWR5IGxvY2tlZCBtdXRleC4KK0lmIHRoZSB0cmFuc2FjdGlv biBob2xkaW5nIHRoZSBsb2NrIGlzIHlvdW5nZXIsIHRoZSBsb2NraW5nIHRyYW5zYWN0aW9uIHdh aXRzLgorSWYgdGhlIHRyYW5zYWN0aW9uIGhvbGRpbmcgdGhlIGxvY2sgaXMgb2xkZXIsIHRoZSBs b2NraW5nIHRyYW5zYWN0aW9uIGJhY2tzIG9mZgorYW5kIGRpZXMuIEhlbmNlIFdhaXQtRGllLgor VGhlcmUgaXMgYWxzbyBhbm90aGVyIGFsZ29yaXRobSBjYWxsZWQgV291bmQtV2FpdDoKK0lmIHRo ZSB0cmFuc2FjdGlvbiBob2xkaW5nIHRoZSBsb2NrIGlzIHlvdW5nZXIsIHRoZSBsb2NraW5nIHRy YW5zYWN0aW9uCit3b3VuZHMgdGhlIHRyYW5zYWN0aW9uIGhvbGRpbmcgdGhlIGxvY2ssIHJlcXVl c3RpbmcgaXQgdG8gZGllLgorSWYgdGhlIHRyYW5zYWN0aW9uIGhvbGRpbmcgdGhlIGxvY2sgaXMg b2xkZXIsIGl0IHdhaXRzIGZvciB0aGUgb3RoZXIKK3RyYW5zYWN0aW9uLiBIZW5jZSBXb3VuZC1X YWl0LgorVGhlIHR3byBhbGdvcml0aG1zIGFyZSBib3RoIGZhaXIgaW4gdGhhdCBhIHRyYW5zYWN0 aW9uIHdpbGwgZXZlbnR1YWxseSBzdWNjZWVkLgorSG93ZXZlciwgdGhlIFdvdW5kLVdhaXQgYWxn b3JpdGhtIGlzIHR5cGljYWxseSBzdGF0ZWQgdG8gZ2VuZXJhdGUgZmV3ZXIgYmFja29mZnMKK2Nv bXBhcmVkIHRvIFdhaXQtRGllLCBidXQgaXMsIG9uIHRoZSBvdGhlciBoYW5kLCBhc3NvY2lhdGVk IHdpdGggbW9yZSB3b3JrIHRoYW4KK1dhaXQtRGllIHdoZW4gcmVjb3ZlcmluZyBmcm9tIGEgYmFj a29mZi4gV291bmQtV2FpdCBpcyBhbHNvIGEgcHJlZW1wdGl2ZQorYWxnb3JpdGhtIGluIHRoYXQg dHJhbnNhY3Rpb25zIGFyZSB3b3VuZGVkIGJ5IG90aGVyIHRyYW5zYWN0aW9ucywgYW5kIHRoYXQK K3JlcXVpcmVzIGEgcmVsaWFibGUgd2F5IHRvIHBpY2sgdXAgdXAgdGhlIHdvdW5kZWQgY29uZGl0 aW9uIGFuZCBwcmVlbXB0IHRoZQorcnVubmluZyB0cmFuc2FjdGlvbi4gTm90ZSB0aGF0IHRoaXMg aXMgbm90IHRoZSBzYW1lIGFzIHByb2Nlc3MgcHJlZW1wdGlvbi4gQQorV291bmQtV2FpdCB0cmFu c2FjdGlvbiBpcyBjb25zaWRlcmVkIHByZWVtcHRlZCB3aGVuIGl0IGRpZXMgKHJldHVybmluZwor LUVERUFETEspIGZvbGxvd2luZyBhIHdvdW5kLgogCiBDb25jZXB0cwogLS0tLS0tLS0KQEAgLTQ3 LDEwICs2MywxMiBAQCBBY3F1aXJlIGNvbnRleHQ6IFRvIGVuc3VyZSBldmVudHVhbCBmb3J3YXJk IHByb2dyZXNzIGl0IGlzIGltcG9ydGFudCB0aGUgYSB0YXNrCiB0cnlpbmcgdG8gYWNxdWlyZSBs b2NrcyBkb2Vzbid0IGdyYWIgYSBuZXcgcmVzZXJ2YXRpb24gaWQsIGJ1dCBrZWVwcyB0aGUgb25l IGl0CiBhY3F1aXJlZCB3aGVuIHN0YXJ0aW5nIHRoZSBsb2NrIGFjcXVpc2l0aW9uLiBUaGlzIHRp Y2tldCBpcyBzdG9yZWQgaW4gdGhlCiBhY3F1aXJlIGNvbnRleHQuIEZ1cnRoZXJtb3JlIHRoZSBh Y3F1aXJlIGNvbnRleHQga2VlcHMgdHJhY2sgb2YgZGVidWdnaW5nIHN0YXRlCi10byBjYXRjaCB3 L3cgbXV0ZXggaW50ZXJmYWNlIGFidXNlLgordG8gY2F0Y2ggdy93IG11dGV4IGludGVyZmFjZSBh YnVzZS4gQW4gYWNxdWlyZSBjb250ZXh0IGlzIHJlcHJlc2VudGluZyBhCit0cmFuc2FjdGlvbi4K IAogVy93IGNsYXNzOiBJbiBjb250cmFzdCB0byBub3JtYWwgbXV0ZXhlcyB0aGUgbG9jayBjbGFz cyBuZWVkcyB0byBiZSBleHBsaWNpdCBmb3IKLXcvdyBtdXRleGVzLCBzaW5jZSBpdCBpcyByZXF1 aXJlZCB0byBpbml0aWFsaXplIHRoZSBhY3F1aXJlIGNvbnRleHQuCit3L3cgbXV0ZXhlcywgc2lu Y2UgaXQgaXMgcmVxdWlyZWQgdG8gaW5pdGlhbGl6ZSB0aGUgYWNxdWlyZSBjb250ZXh0LiBUaGUg bG9jaworY2xhc3MgYWxzbyBzcGVjaWZpZXMgd2hhdCBhbGdvcml0aG0gdG8gdXNlLCBXb3VuZC1X YWl0IG9yIFdhaXQtRGllLgogCiBGdXJ0aGVybW9yZSB0aGVyZSBhcmUgdGhyZWUgZGlmZmVyZW50 IGNsYXNzIG9mIHcvdyBsb2NrIGFjcXVpcmUgZnVuY3Rpb25zOgogCkBAIC05MCw2ICsxMDgsMTIg QEAgcHJvdmlkZWQuCiBVc2FnZQogLS0tLS0KIAorVGhlIGFsZ29yaXRobSAoV2FpdC1EaWUgdnMg V291bmQtV2FpdCkgaXMgY2hvc2VuIGJ5IHVzaW5nIGVpdGhlcgorREVGSU5FX1dXX0NMQVNTKCkg KFdvdW5kLVdhaXQpIG9yIERFRklORV9XRF9DTEFTUygpIChXYWl0LURpZSkKK0FzIGEgcm91Z2gg cnVsZSBvZiB0aHVtYiwgdXNlIFdvdW5kLVdhaXQgaWZmIHlvdQorZXhwZWN0IHRoZSBudW1iZXIg b2Ygc2ltdWx0YW5lb3VzIGNvbXBldGluZyB0cmFuc2FjdGlvbnMgdG8gYmUgdHlwaWNhbGx5IHNt YWxsLAorYW5kIHlvdSB3YW50IHRvIHJlZHVjZSB0aGUgbnVtYmVyIG9mIHJvbGxiYWNrcy4KKwog VGhyZWUgZGlmZmVyZW50IHdheXMgdG8gYWNxdWlyZSBsb2NrcyB3aXRoaW4gdGhlIHNhbWUgdy93 IGNsYXNzLiBDb21tb24KIGRlZmluaXRpb25zIGZvciBtZXRob2RzICMxIGFuZCAjMjoKIApAQCAt MzEyLDEyICszMzYsMjMgQEAgRGVzaWduOgogICBXZSBtYWludGFpbiB0aGUgZm9sbG93aW5nIGlu dmFyaWFudHMgZm9yIHRoZSB3YWl0IGxpc3Q6CiAgICgxKSBXYWl0ZXJzIHdpdGggYW4gYWNxdWly ZSBjb250ZXh0IGFyZSBzb3J0ZWQgYnkgc3RhbXAgb3JkZXI7IHdhaXRlcnMKICAgICAgIHdpdGhv dXQgYW4gYWNxdWlyZSBjb250ZXh0IGFyZSBpbnRlcnNwZXJzZWQgaW4gRklGTyBvcmRlci4KLSAg KDIpIEFtb25nIHdhaXRlcnMgd2l0aCBjb250ZXh0cywgb25seSB0aGUgZmlyc3Qgb25lIGNhbiBo YXZlIG90aGVyIGxvY2tzCi0gICAgICBhY3F1aXJlZCBhbHJlYWR5IChjdHgtPmFjcXVpcmVkID4g MCkuIE5vdGUgdGhhdCB0aGlzIHdhaXRlciBtYXkgY29tZQotICAgICAgYWZ0ZXIgb3RoZXIgd2Fp dGVycyB3aXRob3V0IGNvbnRleHRzIGluIHRoZSBsaXN0LgorICAoMikgRm9yIFdhaXQtRGllLCBh bW9uZyB3YWl0ZXJzIHdpdGggY29udGV4dHMsIG9ubHkgdGhlIGZpcnN0IG9uZSBjYW4gaGF2ZQor ICAgICAgb3RoZXIgbG9ja3MgYWNxdWlyZWQgYWxyZWFkeSAoY3R4LT5hY3F1aXJlZCA+IDApLiBO b3RlIHRoYXQgdGhpcyB3YWl0ZXIKKyAgICAgIG1heSBjb21lIGFmdGVyIG90aGVyIHdhaXRlcnMg d2l0aG91dCBjb250ZXh0cyBpbiB0aGUgbGlzdC4KKworICBUaGUgV291bmQtV2FpdCBwcmVlbXB0 aW9uIGlzIGltcGxlbWVudGVkIHdpdGggYSBsYXp5LXByZWVtcHRpb24gc2NoZW1lOgorICBUaGUg d291bmRlZCBzdGF0dXMgb2YgdGhlIHRyYW5zYWN0aW9uIGlzIGNoZWNrZWQgb25seSB3aGVuIHRo ZXJlIGlzCisgIGNvbnRlbnRpb24gZm9yIGEgbmV3IGxvY2sgYW5kIGhlbmNlIGEgdHJ1ZSBjaGFu Y2Ugb2YgZGVhZGxvY2suIEluIHRoYXQKKyAgc2l0dWF0aW9uLCBpZiB0aGUgdHJhbnNhY3Rpb24g aXMgd291bmRlZCwgaXQgYmFja3Mgb2ZmLCBjbGVhcnMgdGhlCisgIHdvdW5kZWQgc3RhdHVzIGFu ZCByZXRyaWVzLiBBIGdyZWF0IGJlbmVmaXQgb2YgaW1wbGVtZW50aW5nIHByZWVtcHRpb24gaW4K KyAgdGhpcyB3YXkgaXMgdGhhdCB0aGUgd291bmRlZCB0cmFuc2FjdGlvbiBjYW4gaWRlbnRpZnkg YSBjb250ZW5kaW5nIGxvY2sgdG8KKyAgd2FpdCBmb3IgYmVmb3JlIHJlc3RhcnRpbmcgdGhlIHRy YW5zYWN0aW9uLiBKdXN0IGJsaW5kbHkgcmVzdGFydGluZyB0aGUKKyAgdHJhbnNhY3Rpb24gd291 bGQgbGlrZWx5IG1ha2UgdGhlIHRyYW5zYWN0aW9uIGVuZCB1cCBpbiBhIHNpdHVhdGlvbiB3aGVy ZQorICBpdCB3b3VsZCBoYXZlIHRvIGJhY2sgb2ZmIGFnYWluLgogCiAgIEluIGdlbmVyYWwsIG5v dCBtdWNoIGNvbnRlbnRpb24gaXMgZXhwZWN0ZWQuIFRoZSBsb2NrcyBhcmUgdHlwaWNhbGx5IHVz ZWQgdG8KLSAgc2VyaWFsaXplIGFjY2VzcyB0byByZXNvdXJjZXMgZm9yIGRldmljZXMuCisgIHNl cmlhbGl6ZSBhY2Nlc3MgdG8gcmVzb3VyY2VzIGZvciBkZXZpY2VzLCBhbmQgb3B0aW1pemF0aW9u IGZvY3VzIHNob3VsZAorICB0aGVyZWZvcmUgYmUgZGlyZWN0ZWQgdG93YXJkcyB0aGUgdW5jb250 ZW5kZWQgY2FzZXMuCiAKIExvY2tkZXA6CiAgIFNwZWNpYWwgY2FyZSBoYXMgYmVlbiB0YWtlbiB0 byB3YXJuIGZvciBhcyBtYW55IGNhc2VzIG9mIGFwaSBhYnVzZQpkaWZmIC0tZ2l0IGEvZHJpdmVy cy9kbWEtYnVmL3Jlc2VydmF0aW9uLmMgYi9kcml2ZXJzL2RtYS1idWYvcmVzZXJ2YXRpb24uYwpp bmRleCAzMTRlYjEwNzFjY2UuLjIwYmY5MGY0ZWU2MyAxMDA2NDQKLS0tIGEvZHJpdmVycy9kbWEt YnVmL3Jlc2VydmF0aW9uLmMKKysrIGIvZHJpdmVycy9kbWEtYnVmL3Jlc2VydmF0aW9uLmMKQEAg LTQ2LDcgKzQ2LDcgQEAKICAqIHdyaXRlLXNpZGUgdXBkYXRlcy4KICAqLwogCi1ERUZJTkVfV1df Q0xBU1MocmVzZXJ2YXRpb25fd3dfY2xhc3MpOworREVGSU5FX1dEX0NMQVNTKHJlc2VydmF0aW9u X3d3X2NsYXNzKTsKIEVYUE9SVF9TWU1CT0wocmVzZXJ2YXRpb25fd3dfY2xhc3MpOwogCiBzdHJ1 Y3QgbG9ja19jbGFzc19rZXkgcmVzZXJ2YXRpb25fc2VxY291bnRfY2xhc3M7CmRpZmYgLS1naXQg YS9kcml2ZXJzL2dwdS9kcm0vZHJtX21vZGVzZXRfbG9jay5jIGIvZHJpdmVycy9ncHUvZHJtL2Ry bV9tb2Rlc2V0X2xvY2suYwppbmRleCA4YTUxMDA2ODU4NzUuLjYzOGJlMmViNjdiNCAxMDA2NDQK LS0tIGEvZHJpdmVycy9ncHUvZHJtL2RybV9tb2Rlc2V0X2xvY2suYworKysgYi9kcml2ZXJzL2dw dS9kcm0vZHJtX21vZGVzZXRfbG9jay5jCkBAIC03MCw3ICs3MCw3IEBACiAgKiBsaXN0cyBhbmQg bG9va3VwIGRhdGEgc3RydWN0dXJlcy4KICAqLwogCi1zdGF0aWMgREVGSU5FX1dXX0NMQVNTKGNy dGNfd3dfY2xhc3MpOworc3RhdGljIERFRklORV9XRF9DTEFTUyhjcnRjX3d3X2NsYXNzKTsKIAog LyoqCiAgKiBkcm1fbW9kZXNldF9sb2NrX2FsbCAtIHRha2UgYWxsIG1vZGVzZXQgbG9ja3MKZGlm ZiAtLWdpdCBhL2luY2x1ZGUvbGludXgvd3dfbXV0ZXguaCBiL2luY2x1ZGUvbGludXgvd3dfbXV0 ZXguaAppbmRleCBmODJmY2UyMjI5YzguLjNhZjdjMGUwM2JlNSAxMDA2NDQKLS0tIGEvaW5jbHVk ZS9saW51eC93d19tdXRleC5oCisrKyBiL2luY2x1ZGUvbGludXgvd3dfbXV0ZXguaApAQCAtOCw2 ICs4LDggQEAKICAqCiAgKiBXYWl0L0RpZSBpbXBsZW1lbnRhdGlvbjoKICAqICBDb3B5cmlnaHQg KEMpIDIwMTMgQ2Fub25pY2FsIEx0ZC4KKyAqIENob2ljZSBvZiBhbGdvcml0aG06CisgKiAgQ29w eXJpZ2h0IChDKSAyMDE4IFdNV2FyZSBJbmMuCiAgKgogICogVGhpcyBmaWxlIGNvbnRhaW5zIHRo ZSBtYWluIGRhdGEgc3RydWN0dXJlIGFuZCBBUEkgZGVmaW5pdGlvbnMuCiAgKi8KQEAgLTIzLDEy ICsyNSwxNSBAQCBzdHJ1Y3Qgd3dfY2xhc3MgewogCXN0cnVjdCBsb2NrX2NsYXNzX2tleSBtdXRl eF9rZXk7CiAJY29uc3QgY2hhciAqYWNxdWlyZV9uYW1lOwogCWNvbnN0IGNoYXIgKm11dGV4X25h bWU7CisJdW5zaWduZWQgaW50IGlzX3dhaXRfZGllOwogfTsKIAogc3RydWN0IHd3X2FjcXVpcmVf Y3R4IHsKIAlzdHJ1Y3QgdGFza19zdHJ1Y3QgKnRhc2s7CiAJdW5zaWduZWQgbG9uZyBzdGFtcDsK IAl1bnNpZ25lZCBpbnQgYWNxdWlyZWQ7CisJdW5zaWduZWQgc2hvcnQgd291bmRlZDsKKwl1bnNp Z25lZCBzaG9ydCBpc193YWl0X2RpZTsKICNpZmRlZiBDT05GSUdfREVCVUdfTVVURVhFUwogCXVu c2lnbmVkIGludCBkb25lX2FjcXVpcmU7CiAJc3RydWN0IHd3X2NsYXNzICp3d19jbGFzczsKQEAg LTU4LDE3ICs2MywyMSBAQCBzdHJ1Y3Qgd3dfbXV0ZXggewogIyBkZWZpbmUgX19XV19DTEFTU19N VVRFWF9JTklUSUFMSVpFUihsb2NrbmFtZSwgY2xhc3MpCiAjZW5kaWYKIAotI2RlZmluZSBfX1dX X0NMQVNTX0lOSVRJQUxJWkVSKHd3X2NsYXNzKSBcCisjZGVmaW5lIF9fV1dfQ0xBU1NfSU5JVElB TElaRVIod3dfY2xhc3MsIF9pc193YWl0X2RpZSkJICAgIFwKIAkJeyAuc3RhbXAgPSBBVE9NSUNf TE9OR19JTklUKDApIFwKIAkJLCAuYWNxdWlyZV9uYW1lID0gI3d3X2NsYXNzICJfYWNxdWlyZSIg XAotCQksIC5tdXRleF9uYW1lID0gI3d3X2NsYXNzICJfbXV0ZXgiIH0KKwkJLCAubXV0ZXhfbmFt ZSA9ICN3d19jbGFzcyAiX211dGV4IiBcCisJCSwgLmlzX3dhaXRfZGllID0gX2lzX3dhaXRfZGll IH0KIAogI2RlZmluZSBfX1dXX01VVEVYX0lOSVRJQUxJWkVSKGxvY2tuYW1lLCBjbGFzcykgXAog CQl7IC5iYXNlID0gIF9fTVVURVhfSU5JVElBTElaRVIobG9ja25hbWUuYmFzZSkgXAogCQlfX1dX X0NMQVNTX01VVEVYX0lOSVRJQUxJWkVSKGxvY2tuYW1lLCBjbGFzcykgfQogCisjZGVmaW5lIERF RklORV9XRF9DTEFTUyhjbGFzc25hbWUpIFwKKwlzdHJ1Y3Qgd3dfY2xhc3MgY2xhc3NuYW1lID0g X19XV19DTEFTU19JTklUSUFMSVpFUihjbGFzc25hbWUsIDEpCisKICNkZWZpbmUgREVGSU5FX1dX X0NMQVNTKGNsYXNzbmFtZSkgXAotCXN0cnVjdCB3d19jbGFzcyBjbGFzc25hbWUgPSBfX1dXX0NM QVNTX0lOSVRJQUxJWkVSKGNsYXNzbmFtZSkKKwlzdHJ1Y3Qgd3dfY2xhc3MgY2xhc3NuYW1lID0g X19XV19DTEFTU19JTklUSUFMSVpFUihjbGFzc25hbWUsIDApCiAKICNkZWZpbmUgREVGSU5FX1dX X01VVEVYKG11dGV4bmFtZSwgd3dfY2xhc3MpIFwKIAlzdHJ1Y3Qgd3dfbXV0ZXggbXV0ZXhuYW1l ID0gX19XV19NVVRFWF9JTklUSUFMSVpFUihtdXRleG5hbWUsIHd3X2NsYXNzKQpAQCAtMTIzLDYg KzEzMiw4IEBAIHN0YXRpYyBpbmxpbmUgdm9pZCB3d19hY3F1aXJlX2luaXQoc3RydWN0IHd3X2Fj cXVpcmVfY3R4ICpjdHgsCiAJY3R4LT50YXNrID0gY3VycmVudDsKIAljdHgtPnN0YW1wID0gYXRv bWljX2xvbmdfaW5jX3JldHVybl9yZWxheGVkKCZ3d19jbGFzcy0+c3RhbXApOwogCWN0eC0+YWNx dWlyZWQgPSAwOworCWN0eC0+d291bmRlZCA9IGZhbHNlOworCWN0eC0+aXNfd2FpdF9kaWUgPSB3 d19jbGFzcy0+aXNfd2FpdF9kaWU7CiAjaWZkZWYgQ09ORklHX0RFQlVHX01VVEVYRVMKIAljdHgt Pnd3X2NsYXNzID0gd3dfY2xhc3M7CiAJY3R4LT5kb25lX2FjcXVpcmUgPSAwOwpkaWZmIC0tZ2l0 IGEva2VybmVsL2xvY2tpbmcvbG9ja3RvcnR1cmUuYyBiL2tlcm5lbC9sb2NraW5nL2xvY2t0b3J0 dXJlLmMKaW5kZXggNjg1MGZmZDY5MTI1Li45MDdlMDMyNTg5MmMgMTAwNjQ0Ci0tLSBhL2tlcm5l bC9sb2NraW5nL2xvY2t0b3J0dXJlLmMKKysrIGIva2VybmVsL2xvY2tpbmcvbG9ja3RvcnR1cmUu YwpAQCAtMzY1LDcgKzM2NSw3IEBAIHN0YXRpYyBzdHJ1Y3QgbG9ja190b3J0dXJlX29wcyBtdXRl eF9sb2NrX29wcyA9IHsKIH07CiAKICNpbmNsdWRlIDxsaW51eC93d19tdXRleC5oPgotc3RhdGlj IERFRklORV9XV19DTEFTUyh0b3J0dXJlX3d3X2NsYXNzKTsKK3N0YXRpYyBERUZJTkVfV0RfQ0xB U1ModG9ydHVyZV93d19jbGFzcyk7CiBzdGF0aWMgREVGSU5FX1dXX01VVEVYKHRvcnR1cmVfd3df bXV0ZXhfMCwgJnRvcnR1cmVfd3dfY2xhc3MpOwogc3RhdGljIERFRklORV9XV19NVVRFWCh0b3J0 dXJlX3d3X211dGV4XzEsICZ0b3J0dXJlX3d3X2NsYXNzKTsKIHN0YXRpYyBERUZJTkVfV1dfTVVU RVgodG9ydHVyZV93d19tdXRleF8yLCAmdG9ydHVyZV93d19jbGFzcyk7CmRpZmYgLS1naXQgYS9r ZXJuZWwvbG9ja2luZy9tdXRleC5jIGIva2VybmVsL2xvY2tpbmcvbXV0ZXguYwppbmRleCA0MTJi NGZjMDgyMzUuLjhjYTgzYTVlM2QyNCAxMDA2NDQKLS0tIGEva2VybmVsL2xvY2tpbmcvbXV0ZXgu YworKysgYi9rZXJuZWwvbG9ja2luZy9tdXRleC5jCkBAIC0xNzIsNiArMTcyLDIxIEBAIHN0YXRp YyBpbmxpbmUgYm9vbCBfX211dGV4X3dhaXRlcl9pc19maXJzdChzdHJ1Y3QgbXV0ZXggKmxvY2ss IHN0cnVjdCBtdXRleF93YWl0CiAJcmV0dXJuIGxpc3RfZmlyc3RfZW50cnkoJmxvY2stPndhaXRf bGlzdCwgc3RydWN0IG11dGV4X3dhaXRlciwgbGlzdCkgPT0gd2FpdGVyOwogfQogCisvKgorICog QWRkIEB3YWl0ZXIgdG8gYSBnaXZlbiBsb2NhdGlvbiBpbiB0aGUgbG9jayB3YWl0X2xpc3QgYW5k IHNldCB0aGUKKyAqIEZMQUdfV0FJVEVSUyBmbGFnIGlmIGl0J3MgdGhlIGZpcnN0IHdhaXRlci4K KyAqLworc3RhdGljIHZvaWQgX19zY2hlZAorX19tdXRleF9hZGRfd2FpdGVyKHN0cnVjdCBtdXRl eCAqbG9jaywgc3RydWN0IG11dGV4X3dhaXRlciAqd2FpdGVyLAorCQkgICBzdHJ1Y3QgbGlzdF9o ZWFkICpsaXN0KQoreworCWRlYnVnX211dGV4X2FkZF93YWl0ZXIobG9jaywgd2FpdGVyLCBjdXJy ZW50KTsKKworCWxpc3RfYWRkX3RhaWwoJndhaXRlci0+bGlzdCwgbGlzdCk7CisJaWYgKF9fbXV0 ZXhfd2FpdGVyX2lzX2ZpcnN0KGxvY2ssIHdhaXRlcikpCisJCV9fbXV0ZXhfc2V0X2ZsYWcobG9j aywgTVVURVhfRkxBR19XQUlURVJTKTsKK30KKwogLyoKICAqIEdpdmUgdXAgb3duZXJzaGlwIHRv IGEgc3BlY2lmaWMgdGFzaywgd2hlbiBAdGFzayA9IE5VTEwsIHRoaXMgaXMgZXF1aXZhbGVudAog ICogdG8gYSByZWd1bGFyIHVubG9jay4gU2V0cyBQSUNLVVAgb24gYSBoYW5kb2ZmLCBjbGVhcnMg SEFORE9GLCBwcmVzZXJ2ZXMKQEAgLTI0OCw2ICsyNjMsMTEgQEAgRVhQT1JUX1NZTUJPTChtdXRl eF9sb2NrKTsKICAqICAgVGhlIG5ld2VyIHRyYW5zYWN0aW9ucyBhcmUga2lsbGVkIHdoZW46CiAg KiAgICAgSXQgKHRoZSBuZXcgdHJhbnNhY3Rpb24pIG1ha2VzIGEgcmVxdWVzdCBmb3IgYSBsb2Nr IGJlaW5nIGhlbGQKICAqICAgICBieSBhbiBvbGRlciB0cmFuc2FjdGlvbi4KKyAqCisgKiBXb3Vu ZC1XYWl0OgorICogICBUaGUgbmV3ZXIgdHJhbnNhY3Rpb25zIGFyZSB3b3VuZGVkIHdoZW46Cisg KiAgICAgQW4gb2xkZXIgdHJhbnNhY3Rpb24gbWFrZXMgYSByZXF1ZXN0IGZvciBhIGxvY2sgYmVp bmcgaGVsZCBieQorICogICAgIHRoZSBuZXdlciB0cmFuc2FjdGlvbi4KICAqLwogCiAvKgpAQCAt MzE5LDYgKzMzOSw5IEBAIHN0YXRpYyBib29sIF9fc2NoZWQKIF9fd3dfbXV0ZXhfZGllKHN0cnVj dCBtdXRleCAqbG9jaywgc3RydWN0IG11dGV4X3dhaXRlciAqd2FpdGVyLAogCSAgICAgICBzdHJ1 Y3Qgd3dfYWNxdWlyZV9jdHggKnd3X2N0eCkKIHsKKwlpZiAoIXd3X2N0eC0+aXNfd2FpdF9kaWUp CisJCXJldHVybiBmYWxzZTsKKwogCWlmICh3YWl0ZXItPnd3X2N0eC0+YWNxdWlyZWQgPiAwICYm CiAJCQlfX3d3X2N0eF9zdGFtcF9hZnRlcih3YWl0ZXItPnd3X2N0eCwgd3dfY3R4KSkgewogCQlk ZWJ1Z19tdXRleF93YWtlX3dhaXRlcihsb2NrLCB3YWl0ZXIpOwpAQCAtMzI4LDEzICszNTEsNjUg QEAgX193d19tdXRleF9kaWUoc3RydWN0IG11dGV4ICpsb2NrLCBzdHJ1Y3QgbXV0ZXhfd2FpdGVy ICp3YWl0ZXIsCiAJcmV0dXJuIHRydWU7CiB9CiAKKy8qCisgKiBXb3VuZC1XYWl0OyB3b3VuZCBh IHlvdW5nZXIgQGhvbGRfY3R4IGlmIGl0IGhvbGRzIHRoZSBsb2NrLgorICoKKyAqIFdvdW5kIHRo ZSBsb2NrIGhvbGRlciBpZiB0aGVyZSBhcmUgd2FpdGVycyB3aXRoIG9sZGVyIHRyYW5zYWN0aW9u cyB0aGFuCisgKiB0aGUgbG9jayBob2xkZXJzLiBFdmVuIGlmIG11bHRpcGxlIHdhaXRlcnMgbWF5 IHdvdW5kIHRoZSBsb2NrIGhvbGRlciwKKyAqIGl0J3Mgc3VmZmljaWVudCB0aGF0IG9ubHkgb25l IGRvZXMuCisgKi8KK3N0YXRpYyBib29sIF9fd3dfbXV0ZXhfd291bmQoc3RydWN0IG11dGV4ICps b2NrLAorCQkJICAgICBzdHJ1Y3Qgd3dfYWNxdWlyZV9jdHggKnd3X2N0eCwKKwkJCSAgICAgc3Ry dWN0IHd3X2FjcXVpcmVfY3R4ICpob2xkX2N0eCkKK3sKKwlzdHJ1Y3QgdGFza19zdHJ1Y3QgKm93 bmVyID0gX19tdXRleF9vd25lcihsb2NrKTsKKworCWxvY2tkZXBfYXNzZXJ0X2hlbGQoJmxvY2st PndhaXRfbG9jayk7CisKKwkvKgorCSAqIFBvc3NpYmxlIHRocm91Z2ggX193d19tdXRleF9hZGRf d2FpdGVyKCkgd2hlbiB3ZSByYWNlIHdpdGgKKwkgKiB3d19tdXRleF9zZXRfY29udGV4dF9mYXN0 cGF0aCgpLiBJbiB0aGF0IGNhc2Ugd2UnbGwgZ2V0IGhlcmUgYWdhaW4KKwkgKiB0aHJvdWdoIF9f d3dfbXV0ZXhfY2hlY2tfd2FpdGVycygpLgorCSAqLworCWlmICghaG9sZF9jdHgpCisJCXJldHVy biBmYWxzZTsKKworCS8qCisJICogQ2FuIGhhdmUgIW93bmVyIGJlY2F1c2Ugb2YgX19tdXRleF91 bmxvY2tfc2xvd3BhdGgoKSwgYnV0IGlmIG93bmVyLAorCSAqIGl0IGNhbm5vdCBnbyBhd2F5IGJl Y2F1c2Ugd2UnbGwgaGF2ZSBGTEFHX1dBSVRFUlMgc2V0IGFuZCBob2xkCisJICogd2FpdF9sb2Nr LgorCSAqLworCWlmICghb3duZXIpCisJCXJldHVybiBmYWxzZTsKKworCWlmICh3d19jdHgtPmFj cXVpcmVkID4gMCAmJiBfX3d3X2N0eF9zdGFtcF9hZnRlcihob2xkX2N0eCwgd3dfY3R4KSkgewor CQlob2xkX2N0eC0+d291bmRlZCA9IDE7CisKKwkJLyoKKwkJICogd2FrZV91cF9wcm9jZXNzKCkg cGFpcmVkIHdpdGggc2V0X2N1cnJlbnRfc3RhdGUoKQorCQkgKiBpbnNlcnRzIHN1ZmZpY2llbnQg YmFycmllcnMgdG8gbWFrZSBzdXJlIEBvd25lciBlaXRoZXIgc2VlcworCQkgKiBpdCdzIHdvdW5k ZWQgaW4gX193d19tdXRleF9sb2NrX2NoZWNrX3N0YW1wKCkgb3IgaGFzIGEKKwkJICogd2FrZXVw IHBlbmRpbmcgdG8gcmUtcmVhZCB0aGUgd291bmRlZCBzdGF0ZS4KKwkJICovCisJCWlmIChvd25l ciAhPSBjdXJyZW50KQorCQkJd2FrZV91cF9wcm9jZXNzKG93bmVyKTsKKworCQlyZXR1cm4gdHJ1 ZTsKKwl9CisKKwlyZXR1cm4gZmFsc2U7Cit9CisKIC8qCiAgKiBXZSBqdXN0IGFjcXVpcmVkIEBs b2NrIHVuZGVyIEB3d19jdHgsIGlmIHRoZXJlIGFyZSBsYXRlciBjb250ZXh0cyB3YWl0aW5nCi0g KiBiZWhpbmQgdXMgb24gdGhlIHdhaXQtbGlzdCwgY2hlY2sgaWYgdGhleSBuZWVkIHRvIGRpZS4K KyAqIGJlaGluZCB1cyBvbiB0aGUgd2FpdC1saXN0LCBjaGVjayBpZiB0aGV5IG5lZWQgdG8gZGll LCBvciB3b3VuZCB1cy4KICAqCiAgKiBTZWUgX193d19tdXRleF9hZGRfd2FpdGVyKCkgZm9yIHRo ZSBsaXN0LW9yZGVyIGNvbnN0cnVjdGlvbjsgYmFzaWNhbGx5IHRoZQogICogbGlzdCBpcyBvcmRl cmVkIGJ5IHN0YW1wLCBzbWFsbGVzdCAob2xkZXN0KSBmaXJzdC4KICAqCisgKiBUaGlzIHJlbGll cyBvbiBuZXZlciBtaXhpbmcgd2FpdC1kaWUvd291bmQtd2FpdCBvbiB0aGUgc2FtZSB3YWl0LWxp c3Q7CisgKiB3aGljaCBpcyBjdXJyZW50bHkgZW5zdXJlZCBieSB0aGF0IGJlaW5nIGEgd3dfY2xh c3MgcHJvcGVydHkuCisgKgogICogVGhlIGN1cnJlbnQgdGFzayBtdXN0IG5vdCBiZSBvbiB0aGUg d2FpdCBsaXN0LgogICovCiBzdGF0aWMgdm9pZCBfX3NjaGVkCkBAIC0zNDgsNyArNDIzLDggQEAg X193d19tdXRleF9jaGVja193YWl0ZXJzKHN0cnVjdCBtdXRleCAqbG9jaywgc3RydWN0IHd3X2Fj cXVpcmVfY3R4ICp3d19jdHgpCiAJCWlmICghY3VyLT53d19jdHgpCiAJCQljb250aW51ZTsKIAot CQlpZiAoX193d19tdXRleF9kaWUobG9jaywgY3VyLCB3d19jdHgpKQorCQlpZiAoX193d19tdXRl eF9kaWUobG9jaywgY3VyLCB3d19jdHgpIHx8CisJCSAgICBfX3d3X211dGV4X3dvdW5kKGxvY2ss IGN1ci0+d3dfY3R4LCB3d19jdHgpKQogCQkJYnJlYWs7CiAJfQogfQpAQCAtMzY5LDE3ICs0NDUs MjMgQEAgd3dfbXV0ZXhfc2V0X2NvbnRleHRfZmFzdHBhdGgoc3RydWN0IHd3X211dGV4ICpsb2Nr LCBzdHJ1Y3Qgd3dfYWNxdWlyZV9jdHggKmN0eCkKIAkgKiBhbmQga2VlcCBzcGlubmluZywgb3Ig aXQgd2lsbCBhY3F1aXJlIHdhaXRfbG9jaywgYWRkIGl0c2VsZgogCSAqIHRvIHdhaXRlciBsaXN0 IGFuZCBzbGVlcC4KIAkgKi8KLQlzbXBfbWIoKTsgLyogXl5eICovCisJc21wX21iKCk7IC8qIFNl ZSBjb21tZW50cyBhYm92ZSBhbmQgYmVsb3cuICovCiAKIAkvKgotCSAqIENoZWNrIGlmIGxvY2sg aXMgY29udGVuZGVkLCBpZiBub3QgdGhlcmUgaXMgbm9ib2R5IHRvIHdha2UgdXAKKwkgKiBbV10g d3ctPmN0eCA9IGN0eAkgICAgW1ddIE1VVEVYX0ZMQUdfV0FJVEVSUworCSAqICAgICBNQgkJICAg ICAgICBNQgorCSAqIFtSXSBNVVRFWF9GTEFHX1dBSVRFUlMgICBbUl0gd3ctPmN0eAorCSAqCisJ ICogVGhlIG1lbW9yeSBiYXJyaWVyIGFib3ZlIHBhaXJzIHdpdGggdGhlIG1lbW9yeSBiYXJyaWVy IGluCisJICogX193d19tdXRleF9hZGRfd2FpdGVyKCkgYW5kIG1ha2VzIHN1cmUgd2UgZWl0aGVy IG9ic2VydmUgd3ctPmN0eAorCSAqIGFuZC9vciAhZW1wdHkgbGlzdC4KIAkgKi8KIAlpZiAobGlr ZWx5KCEoYXRvbWljX2xvbmdfcmVhZCgmbG9jay0+YmFzZS5vd25lcikgJiBNVVRFWF9GTEFHX1dB SVRFUlMpKSkKIAkJcmV0dXJuOwogCiAJLyoKIAkgKiBVaCBvaCwgd2UgcmFjZWQgaW4gZmFzdHBh dGgsIGNoZWNrIGlmIGFueSBvZiB0aGUgd2FpdGVycyBuZWVkIHRvCi0JICogZGllLgorCSAqIGRp ZSBvciB3b3VuZCB1cy4KIAkgKi8KIAlzcGluX2xvY2soJmxvY2stPmJhc2Uud2FpdF9sb2NrKTsK IAlfX3d3X211dGV4X2NoZWNrX3dhaXRlcnMoJmxvY2stPmJhc2UsIGN0eCk7CkBAIC02ODEsNyAr NzYzLDkgQEAgX193d19tdXRleF9raWxsKHN0cnVjdCBtdXRleCAqbG9jaywgc3RydWN0IHd3X2Fj cXVpcmVfY3R4ICp3d19jdHgpCiAKIAogLyoKLSAqIENoZWNrIHdoZXRoZXIgd2UgbmVlZCB0byBr aWxsIHRoZSB0cmFuc2FjdGlvbiBmb3IgdGhlIGN1cnJlbnQgbG9jayBhY3F1aXJlLgorICogQ2hl Y2sgdGhlIHdvdW5kIGNvbmRpdGlvbiBmb3IgdGhlIGN1cnJlbnQgbG9jayBhY3F1aXJlLgorICoK KyAqIFdvdW5kLVdhaXQ6IElmIHdlJ3JlIHdvdW5kZWQsIGtpbGwgb3Vyc2VsZi4KICAqCiAgKiBX YWl0LURpZTogSWYgd2UncmUgdHJ5aW5nIHRvIGFjcXVpcmUgYSBsb2NrIGFscmVhZHkgaGVsZCBi eSBhbiBvbGRlcgogICogICAgICAgICAgIGNvbnRleHQsIGtpbGwgb3Vyc2VsdmVzLgpAQCAtNzAw LDYgKzc4NCwxMyBAQCBfX3d3X211dGV4X2NoZWNrX2tpbGwoc3RydWN0IG11dGV4ICpsb2NrLCBz dHJ1Y3QgbXV0ZXhfd2FpdGVyICp3YWl0ZXIsCiAJaWYgKGN0eC0+YWNxdWlyZWQgPT0gMCkKIAkJ cmV0dXJuIDA7CiAKKwlpZiAoIWN0eC0+aXNfd2FpdF9kaWUpIHsKKwkJaWYgKGN0eC0+d291bmRl ZCkKKwkJCXJldHVybiBfX3d3X211dGV4X2tpbGwobG9jaywgY3R4KTsKKworCQlyZXR1cm4gMDsK Kwl9CisKIAlpZiAoaG9sZF9jdHggJiYgX193d19jdHhfc3RhbXBfYWZ0ZXIoY3R4LCBob2xkX2N0 eCkpCiAJCXJldHVybiBfX3d3X211dGV4X2tpbGwobG9jaywgY3R4KTsKIApAQCAtNzI2LDcgKzgx Nyw4IEBAIF9fd3dfbXV0ZXhfY2hlY2tfa2lsbChzdHJ1Y3QgbXV0ZXggKmxvY2ssIHN0cnVjdCBt dXRleF93YWl0ZXIgKndhaXRlciwKICAqIFdhaXRlcnMgd2l0aG91dCBjb250ZXh0IGFyZSBpbnRl cnNwZXJzZWQgaW4gRklGTyBvcmRlci4KICAqCiAgKiBGdXJ0aGVybW9yZSwgZm9yIFdhaXQtRGll IGtpbGwgb3Vyc2VsZiBpbW1lZGlhdGVseSB3aGVuIHBvc3NpYmxlICh0aGVyZSBhcmUKLSAqIG9s ZGVyIGNvbnRleHRzIGFscmVhZHkgd2FpdGluZykgdG8gYXZvaWQgdW5uZWNlc3Nhcnkgd2FpdGlu Zy4KKyAqIG9sZGVyIGNvbnRleHRzIGFscmVhZHkgd2FpdGluZykgdG8gYXZvaWQgdW5uZWNlc3Nh cnkgd2FpdGluZyBhbmQgZm9yCisgKiBXb3VuZC1XYWl0IGVuc3VyZSB3ZSB3b3VuZCB0aGUgb3du aW5nIGNvbnRleHQgd2hlbiBpdCBpcyB5b3VuZ2VyLgogICovCiBzdGF0aWMgaW5saW5lIGludCBf X3NjaGVkCiBfX3d3X211dGV4X2FkZF93YWl0ZXIoc3RydWN0IG11dGV4X3dhaXRlciAqd2FpdGVy LApAQCAtNzM1LDE2ICs4MjcsMjEgQEAgX193d19tdXRleF9hZGRfd2FpdGVyKHN0cnVjdCBtdXRl eF93YWl0ZXIgKndhaXRlciwKIHsKIAlzdHJ1Y3QgbXV0ZXhfd2FpdGVyICpjdXI7CiAJc3RydWN0 IGxpc3RfaGVhZCAqcG9zOworCWJvb2wgaXNfd2FpdF9kaWU7CiAKIAlpZiAoIXd3X2N0eCkgewot CQlsaXN0X2FkZF90YWlsKCZ3YWl0ZXItPmxpc3QsICZsb2NrLT53YWl0X2xpc3QpOworCQlfX211 dGV4X2FkZF93YWl0ZXIobG9jaywgd2FpdGVyLCAmbG9jay0+d2FpdF9saXN0KTsKIAkJcmV0dXJu IDA7CiAJfQogCisJaXNfd2FpdF9kaWUgPSB3d19jdHgtPmlzX3dhaXRfZGllOworCiAJLyoKIAkg KiBBZGQgdGhlIHdhaXRlciBiZWZvcmUgdGhlIGZpcnN0IHdhaXRlciB3aXRoIGEgaGlnaGVyIHN0 YW1wLgogCSAqIFdhaXRlcnMgd2l0aG91dCBhIGNvbnRleHQgYXJlIHNraXBwZWQgdG8gYXZvaWQg c3RhcnZpbmcKLQkgKiB0aGVtLiBXYWl0LURpZSB3YWl0ZXJzIG1heSBkaWUgaGVyZS4KKwkgKiB0 aGVtLiBXYWl0LURpZSB3YWl0ZXJzIG1heSBkaWUgaGVyZS4gV291bmQtV2FpdCB3YWl0ZXJzCisJ ICogbmV2ZXIgZGllIGhlcmUsIGJ1dCB0aGV5IGFyZSBzb3J0ZWQgaW4gc3RhbXAgb3JkZXIgYW5k CisJICogbWF5IHdvdW5kIHRoZSBsb2NrIGhvbGRlci4KIAkgKi8KIAlwb3MgPSAmbG9jay0+d2Fp dF9saXN0OwogCWxpc3RfZm9yX2VhY2hfZW50cnlfcmV2ZXJzZShjdXIsICZsb2NrLT53YWl0X2xp c3QsIGxpc3QpIHsKQEAgLTc1NywxMCArODU0LDEyIEBAIF9fd3dfbXV0ZXhfYWRkX3dhaXRlcihz dHJ1Y3QgbXV0ZXhfd2FpdGVyICp3YWl0ZXIsCiAJCQkgKiBpcyBubyBwb2ludCBpbiBxdWV1ZWlu ZyBiZWhpbmQgaXQsIGFzIHdlJ2QgaGF2ZSB0bwogCQkJICogZGllIHRoZSBtb21lbnQgaXQgd291 bGQgYWNxdWlyZSB0aGUgbG9jay4KIAkJCSAqLwotCQkJaW50IHJldCA9IF9fd3dfbXV0ZXhfa2ls bChsb2NrLCB3d19jdHgpOworCQkJaWYgKGlzX3dhaXRfZGllKSB7CisJCQkJaW50IHJldCA9IF9f d3dfbXV0ZXhfa2lsbChsb2NrLCB3d19jdHgpOwogCi0JCQlpZiAocmV0KQotCQkJCXJldHVybiBy ZXQ7CisJCQkJaWYgKHJldCkKKwkJCQkJcmV0dXJuIHJldDsKKwkJCX0KIAogCQkJYnJlYWs7CiAJ CX0KQEAgLTc3MSw3ICs4NzAsMjMgQEAgX193d19tdXRleF9hZGRfd2FpdGVyKHN0cnVjdCBtdXRl eF93YWl0ZXIgKndhaXRlciwKIAkJX193d19tdXRleF9kaWUobG9jaywgY3VyLCB3d19jdHgpOwog CX0KIAotCWxpc3RfYWRkX3RhaWwoJndhaXRlci0+bGlzdCwgcG9zKTsKKwlfX211dGV4X2FkZF93 YWl0ZXIobG9jaywgd2FpdGVyLCBwb3MpOworCisJLyoKKwkgKiBXb3VuZC1XYWl0OiBpZiB3ZSdy ZSBibG9ja2luZyBvbiBhIG11dGV4IG93bmVkIGJ5IGEgeW91bmdlciBjb250ZXh0LAorCSAqIHdv dW5kIHRoYXQgc3VjaCB0aGF0IHdlIG1pZ2h0IHByb2NlZWQuCisJICovCisJaWYgKCFpc193YWl0 X2RpZSkgeworCQlzdHJ1Y3Qgd3dfbXV0ZXggKnd3ID0gY29udGFpbmVyX29mKGxvY2ssIHN0cnVj dCB3d19tdXRleCwgYmFzZSk7CisKKwkJLyoKKwkJICogU2VlIHd3X211dGV4X3NldF9jb250ZXh0 X2Zhc3RwYXRoKCkuIE9yZGVycyBzZXR0aW5nCisJCSAqIE1VVEVYX0ZMQUdfV0FJVEVSUyB2cyB0 aGUgd3ctPmN0eCBsb2FkLAorCQkgKiBzdWNoIHRoYXQgZWl0aGVyIHdlIG9yIHRoZSBmYXN0cGF0 aCB3aWxsIHdvdW5kIEB3dy0+Y3R4LgorCQkgKi8KKwkJc21wX21iKCk7CisJCV9fd3dfbXV0ZXhf d291bmQobG9jaywgd3dfY3R4LCB3dy0+Y3R4KTsKKwl9CiAKIAlyZXR1cm4gMDsKIH0KQEAgLTc5 NSw2ICs5MTAsMTQgQEAgX19tdXRleF9sb2NrX2NvbW1vbihzdHJ1Y3QgbXV0ZXggKmxvY2ssIGxv bmcgc3RhdGUsIHVuc2lnbmVkIGludCBzdWJjbGFzcywKIAlpZiAodXNlX3d3X2N0eCAmJiB3d19j dHgpIHsKIAkJaWYgKHVubGlrZWx5KHd3X2N0eCA9PSBSRUFEX09OQ0Uod3ctPmN0eCkpKQogCQkJ cmV0dXJuIC1FQUxSRUFEWTsKKworCQkvKgorCQkgKiBSZXNldCB0aGUgd291bmRlZCBmbGFnIGFm dGVyIGEga2lsbC4gTm8gb3RoZXIgcHJvY2VzcyBjYW4KKwkJICogcmFjZSBhbmQgd291bmQgdXMg aGVyZSBzaW5jZSB0aGV5IGNhbid0IGhhdmUgYSB2YWxpZCBvd25lcgorCQkgKiBwb2ludGVyIGlm IHdlIGRvbid0IGhhdmUgYW55IGxvY2tzIGhlbGQuCisJCSAqLworCQlpZiAod3dfY3R4LT5hY3F1 aXJlZCA9PSAwKQorCQkJd3dfY3R4LT53b3VuZGVkID0gMDsKIAl9CiAKIAlwcmVlbXB0X2Rpc2Fi bGUoKTsKQEAgLTgyOCw3ICs5NTEsOCBAQCBfX211dGV4X2xvY2tfY29tbW9uKHN0cnVjdCBtdXRl eCAqbG9jaywgbG9uZyBzdGF0ZSwgdW5zaWduZWQgaW50IHN1YmNsYXNzLAogCiAJaWYgKCF1c2Vf d3dfY3R4KSB7CiAJCS8qIGFkZCB3YWl0aW5nIHRhc2tzIHRvIHRoZSBlbmQgb2YgdGhlIHdhaXRx dWV1ZSAoRklGTyk6ICovCi0JCWxpc3RfYWRkX3RhaWwoJndhaXRlci5saXN0LCAmbG9jay0+d2Fp dF9saXN0KTsKKwkJX19tdXRleF9hZGRfd2FpdGVyKGxvY2ssICZ3YWl0ZXIsICZsb2NrLT53YWl0 X2xpc3QpOworCiAKICNpZmRlZiBDT05GSUdfREVCVUdfTVVURVhFUwogCQl3YWl0ZXIud3dfY3R4 ID0gTVVURVhfUE9JU09OX1dXX0NUWDsKQEAgLTg0Nyw5ICs5NzEsNiBAQCBfX211dGV4X2xvY2tf Y29tbW9uKHN0cnVjdCBtdXRleCAqbG9jaywgbG9uZyBzdGF0ZSwgdW5zaWduZWQgaW50IHN1YmNs YXNzLAogCiAJd2FpdGVyLnRhc2sgPSBjdXJyZW50OwogCi0JaWYgKF9fbXV0ZXhfd2FpdGVyX2lz X2ZpcnN0KGxvY2ssICZ3YWl0ZXIpKQotCQlfX211dGV4X3NldF9mbGFnKGxvY2ssIE1VVEVYX0ZM QUdfV0FJVEVSUyk7Ci0KIAlzZXRfY3VycmVudF9zdGF0ZShzdGF0ZSk7CiAJZm9yICg7Oykgewog CQkvKgpAQCAtOTA2LDYgKzEwMjcsMTYgQEAgX19tdXRleF9sb2NrX2NvbW1vbihzdHJ1Y3QgbXV0 ZXggKmxvY2ssIGxvbmcgc3RhdGUsIHVuc2lnbmVkIGludCBzdWJjbGFzcywKIGFjcXVpcmVkOgog CV9fc2V0X2N1cnJlbnRfc3RhdGUoVEFTS19SVU5OSU5HKTsKIAorCWlmICh1c2Vfd3dfY3R4ICYm IHd3X2N0eCkgeworCQkvKgorCQkgKiBXb3VuZC1XYWl0OyB3ZSBzdG9sZSB0aGUgbG9jayAoIWZp cnN0X3dhaXRlciksIGNoZWNrIHRoZQorCQkgKiB3YWl0ZXJzIGFzIGFueW9uZSBtaWdodCB3YW50 IHRvIHdvdW5kIHVzLgorCQkgKi8KKwkJaWYgKCF3d19jdHgtPmlzX3dhaXRfZGllICYmCisJCSAg ICAhX19tdXRleF93YWl0ZXJfaXNfZmlyc3QobG9jaywgJndhaXRlcikpCisJCQlfX3d3X211dGV4 X2NoZWNrX3dhaXRlcnMobG9jaywgd3dfY3R4KTsKKwl9CisKIAltdXRleF9yZW1vdmVfd2FpdGVy KGxvY2ssICZ3YWl0ZXIsIGN1cnJlbnQpOwogCWlmIChsaWtlbHkobGlzdF9lbXB0eSgmbG9jay0+ d2FpdF9saXN0KSkpCiAJCV9fbXV0ZXhfY2xlYXJfZmxhZyhsb2NrLCBNVVRFWF9GTEFHUyk7CmRp ZmYgLS1naXQgYS9rZXJuZWwvbG9ja2luZy90ZXN0LXd3X211dGV4LmMgYi9rZXJuZWwvbG9ja2lu Zy90ZXN0LXd3X211dGV4LmMKaW5kZXggMGU0Y2Q2NGFkMmMwLi41YjkxNWIzNzBkNWEgMTAwNjQ0 Ci0tLSBhL2tlcm5lbC9sb2NraW5nL3Rlc3Qtd3dfbXV0ZXguYworKysgYi9rZXJuZWwvbG9ja2lu Zy90ZXN0LXd3X211dGV4LmMKQEAgLTI2LDcgKzI2LDcgQEAKICNpbmNsdWRlIDxsaW51eC9zbGFi Lmg+CiAjaW5jbHVkZSA8bGludXgvd3dfbXV0ZXguaD4KIAotc3RhdGljIERFRklORV9XV19DTEFT Uyh3d19jbGFzcyk7CitzdGF0aWMgREVGSU5FX1dEX0NMQVNTKHd3X2NsYXNzKTsKIHN0cnVjdCB3 b3JrcXVldWVfc3RydWN0ICp3cTsKIAogc3RydWN0IHRlc3RfbXV0ZXggewpkaWZmIC0tZ2l0IGEv bGliL2xvY2tpbmctc2VsZnRlc3QuYyBiL2xpYi9sb2NraW5nLXNlbGZ0ZXN0LmMKaW5kZXggYjVj MTI5M2NlMTQ3Li4xZTFiYmYxNzFlY2EgMTAwNjQ0Ci0tLSBhL2xpYi9sb2NraW5nLXNlbGZ0ZXN0 LmMKKysrIGIvbGliL2xvY2tpbmctc2VsZnRlc3QuYwpAQCAtMjksNyArMjksNyBAQAogICovCiBz dGF0aWMgdW5zaWduZWQgaW50IGRlYnVnX2xvY2tzX3ZlcmJvc2U7CiAKLXN0YXRpYyBERUZJTkVf V1dfQ0xBU1Mod3dfbG9ja2RlcCk7CitzdGF0aWMgREVGSU5FX1dEX0NMQVNTKHd3X2xvY2tkZXAp OwogCiBzdGF0aWMgaW50IF9faW5pdCBzZXR1cF9kZWJ1Z19sb2Nrc192ZXJib3NlKGNoYXIgKnN0 cikKIHsKLS0gCjIuMTQuMwoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX19fX18KZHJpLWRldmVsIG1haWxpbmcgbGlzdApkcmktZGV2ZWxAbGlzdHMuZnJlZWRlc2t0 b3Aub3JnCmh0dHBzOi8vbGlzdHMuZnJlZWRlc2t0b3Aub3JnL21haWxtYW4vbGlzdGluZm8vZHJp LWRldmVsCg== From mboxrd@z Thu Jan 1 00:00:00 1970 Return-path: Received: from mail-co1nam03on0057.outbound.protection.outlook.com ([104.47.40.57]:50284 "EHLO NAM03-CO1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1756648AbeFSI0J (ORCPT ); Tue, 19 Jun 2018 04:26:09 -0400 From: Thomas Hellstrom To: dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, peterz@infradead.org Cc: linux-graphics-maintainer@vmware.com, pv-drivers@vmware.com, Thomas Hellstrom , Ingo Molnar , Jonathan Corbet , Gustavo Padovan , Maarten Lankhorst , Sean Paul , David Airlie , Davidlohr Bueso , "Paul E. McKenney" , Josh Triplett , Thomas Gleixner , Kate Stewart , Philippe Ombredanne , Greg Kroah-Hartman , linux-doc@vger.kernel.org, linux-media@vger.kernel.org, linaro-mm-sig@lists.linaro.org Subject: [PATCH v4 2/3] locking: Implement an algorithm choice for Wound-Wait mutexes Date: Tue, 19 Jun 2018 10:24:44 +0200 Message-Id: <20180619082445.11062-3-thellstrom@vmware.com> In-Reply-To: <20180619082445.11062-1-thellstrom@vmware.com> References: <20180619082445.11062-1-thellstrom@vmware.com> MIME-Version: 1.0 Content-Type: text/plain Sender: linux-media-owner@vger.kernel.org List-ID: The current Wound-Wait mutex algorithm is actually not Wound-Wait but Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait is, contrary to Wait-Die a preemptive algorithm and is known to generate fewer backoffs. Testing reveals that this is true if the number of simultaneous contending transactions is small. As the number of simultaneous contending threads increases, Wait-Wound becomes inferior to Wait-Die in terms of elapsed time. Possibly due to the larger number of held locks of sleeping transactions. Update documentation and callers. Timings using git://people.freedesktop.org/~thomash/ww_mutex_test tag patch-18-06-15 Each thread runs 100000 batches of lock / unlock 800 ww mutexes randomly chosen out of 100000. Four core Intel x86_64: Algorithm #threads Rollbacks time Wound-Wait 4 ~100 ~17s. Wait-Die 4 ~150000 ~19s. Wound-Wait 16 ~360000 ~109s. Wait-Die 16 ~450000 ~82s. Cc: Ingo Molnar Cc: Jonathan Corbet Cc: Gustavo Padovan Cc: Maarten Lankhorst Cc: Sean Paul Cc: David Airlie Cc: Davidlohr Bueso Cc: "Paul E. McKenney" Cc: Josh Triplett Cc: Thomas Gleixner Cc: Kate Stewart Cc: Philippe Ombredanne Cc: Greg Kroah-Hartman Cc: linux-doc@vger.kernel.org Cc: linux-media@vger.kernel.org Cc: linaro-mm-sig@lists.linaro.org Co-authored-by: Peter Zijlstra Signed-off-by: Thomas Hellstrom --- v2: * Update API according to review comment by Greg Kroah-Hartman. * Address review comments by Peter Zijlstra: - Avoid _Bool in composites - Fix typo - Use __mutex_owner() where applicable - Rely on built-in barriers for the main loop exit condition, struct ww_acquire_ctx::wounded. Update code comments. - Explain unlocked use of list_empty(). v3: * Adapt to and incorporate cleanup by Peter Zijlstra * Remove unlocked use of list_empty(). v4: * Move code related to adding a waiter to the lock waiter list to a separate function. --- Documentation/locking/ww-mutex-design.txt | 57 +++++++++-- drivers/dma-buf/reservation.c | 2 +- drivers/gpu/drm/drm_modeset_lock.c | 2 +- include/linux/ww_mutex.h | 17 ++- kernel/locking/locktorture.c | 2 +- kernel/locking/mutex.c | 165 +++++++++++++++++++++++++++--- kernel/locking/test-ww_mutex.c | 2 +- lib/locking-selftest.c | 2 +- 8 files changed, 213 insertions(+), 36 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 2fd7f2a2af21..f0ed7c30e695 100644 --- a/Documentation/locking/ww-mutex-design.txt +++ b/Documentation/locking/ww-mutex-design.txt @@ -1,4 +1,4 @@ -Wait/Wound Deadlock-Proof Mutex Design +Wound/Wait Deadlock-Proof Mutex Design ====================================== Please read mutex-design.txt first, as it applies to wait/wound mutexes too. @@ -32,10 +32,26 @@ the oldest task) wins, and the one with the higher reservation id (i.e. the younger task) unlocks all of the buffers that it has already locked, and then tries again. -In the RDBMS literature this deadlock handling approach is called wait/die: -The older tasks waits until it can acquire the contended lock. The younger tasks -needs to back off and drop all the locks it is currently holding, i.e. the -younger task dies. +In the RDBMS literature, a reservation ticket is associated with a transaction. +and the deadlock handling approach is called Wait-Die. The name is based on +the actions of a locking thread when it encounters an already locked mutex. +If the transaction holding the lock is younger, the locking transaction waits. +If the transaction holding the lock is older, the locking transaction backs off +and dies. Hence Wait-Die. +There is also another algorithm called Wound-Wait: +If the transaction holding the lock is younger, the locking transaction +wounds the transaction holding the lock, requesting it to die. +If the transaction holding the lock is older, it waits for the other +transaction. Hence Wound-Wait. +The two algorithms are both fair in that a transaction will eventually succeed. +However, the Wound-Wait algorithm is typically stated to generate fewer backoffs +compared to Wait-Die, but is, on the other hand, associated with more work than +Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive +algorithm in that transactions are wounded by other transactions, and that +requires a reliable way to pick up up the wounded condition and preempt the +running transaction. Note that this is not the same as process preemption. A +Wound-Wait transaction is considered preempted when it dies (returning +-EDEADLK) following a wound. Concepts -------- @@ -47,10 +63,12 @@ Acquire context: To ensure eventual forward progress it is important the a task trying to acquire locks doesn't grab a new reservation id, but keeps the one it acquired when starting the lock acquisition. This ticket is stored in the acquire context. Furthermore the acquire context keeps track of debugging state -to catch w/w mutex interface abuse. +to catch w/w mutex interface abuse. An acquire context is representing a +transaction. W/w class: In contrast to normal mutexes the lock class needs to be explicit for -w/w mutexes, since it is required to initialize the acquire context. +w/w mutexes, since it is required to initialize the acquire context. The lock +class also specifies what algorithm to use, Wound-Wait or Wait-Die. Furthermore there are three different class of w/w lock acquire functions: @@ -90,6 +108,12 @@ provided. Usage ----- +The algorithm (Wait-Die vs Wound-Wait) is chosen by using either +DEFINE_WW_CLASS() (Wound-Wait) or DEFINE_WD_CLASS() (Wait-Die) +As a rough rule of thumb, use Wound-Wait iff you +expect the number of simultaneous competing transactions to be typically small, +and you want to reduce the number of rollbacks. + Three different ways to acquire locks within the same w/w class. Common definitions for methods #1 and #2: @@ -312,12 +336,23 @@ Design: We maintain the following invariants for the wait list: (1) Waiters with an acquire context are sorted by stamp order; waiters without an acquire context are interspersed in FIFO order. - (2) Among waiters with contexts, only the first one can have other locks - acquired already (ctx->acquired > 0). Note that this waiter may come - after other waiters without contexts in the list. + (2) For Wait-Die, among waiters with contexts, only the first one can have + other locks acquired already (ctx->acquired > 0). Note that this waiter + may come after other waiters without contexts in the list. + + The Wound-Wait preemption is implemented with a lazy-preemption scheme: + The wounded status of the transaction is checked only when there is + contention for a new lock and hence a true chance of deadlock. In that + situation, if the transaction is wounded, it backs off, clears the + wounded status and retries. A great benefit of implementing preemption in + this way is that the wounded transaction can identify a contending lock to + wait for before restarting the transaction. Just blindly restarting the + transaction would likely make the transaction end up in a situation where + it would have to back off again. In general, not much contention is expected. The locks are typically used to - serialize access to resources for devices. + serialize access to resources for devices, and optimization focus should + therefore be directed towards the uncontended cases. Lockdep: Special care has been taken to warn for as many cases of api abuse diff --git a/drivers/dma-buf/reservation.c b/drivers/dma-buf/reservation.c index 314eb1071cce..20bf90f4ee63 100644 --- a/drivers/dma-buf/reservation.c +++ b/drivers/dma-buf/reservation.c @@ -46,7 +46,7 @@ * write-side updates. */ -DEFINE_WW_CLASS(reservation_ww_class); +DEFINE_WD_CLASS(reservation_ww_class); EXPORT_SYMBOL(reservation_ww_class); struct lock_class_key reservation_seqcount_class; diff --git a/drivers/gpu/drm/drm_modeset_lock.c b/drivers/gpu/drm/drm_modeset_lock.c index 8a5100685875..638be2eb67b4 100644 --- a/drivers/gpu/drm/drm_modeset_lock.c +++ b/drivers/gpu/drm/drm_modeset_lock.c @@ -70,7 +70,7 @@ * lists and lookup data structures. */ -static DEFINE_WW_CLASS(crtc_ww_class); +static DEFINE_WD_CLASS(crtc_ww_class); /** * drm_modeset_lock_all - take all modeset locks diff --git a/include/linux/ww_mutex.h b/include/linux/ww_mutex.h index f82fce2229c8..3af7c0e03be5 100644 --- a/include/linux/ww_mutex.h +++ b/include/linux/ww_mutex.h @@ -8,6 +8,8 @@ * * Wait/Die implementation: * Copyright (C) 2013 Canonical Ltd. + * Choice of algorithm: + * Copyright (C) 2018 WMWare Inc. * * This file contains the main data structure and API definitions. */ @@ -23,12 +25,15 @@ struct ww_class { struct lock_class_key mutex_key; const char *acquire_name; const char *mutex_name; + unsigned int is_wait_die; }; struct ww_acquire_ctx { struct task_struct *task; unsigned long stamp; unsigned int acquired; + unsigned short wounded; + unsigned short is_wait_die; #ifdef CONFIG_DEBUG_MUTEXES unsigned int done_acquire; struct ww_class *ww_class; @@ -58,17 +63,21 @@ struct ww_mutex { # define __WW_CLASS_MUTEX_INITIALIZER(lockname, class) #endif -#define __WW_CLASS_INITIALIZER(ww_class) \ +#define __WW_CLASS_INITIALIZER(ww_class, _is_wait_die) \ { .stamp = ATOMIC_LONG_INIT(0) \ , .acquire_name = #ww_class "_acquire" \ - , .mutex_name = #ww_class "_mutex" } + , .mutex_name = #ww_class "_mutex" \ + , .is_wait_die = _is_wait_die } #define __WW_MUTEX_INITIALIZER(lockname, class) \ { .base = __MUTEX_INITIALIZER(lockname.base) \ __WW_CLASS_MUTEX_INITIALIZER(lockname, class) } +#define DEFINE_WD_CLASS(classname) \ + struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 1) + #define DEFINE_WW_CLASS(classname) \ - struct ww_class classname = __WW_CLASS_INITIALIZER(classname) + struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 0) #define DEFINE_WW_MUTEX(mutexname, ww_class) \ struct ww_mutex mutexname = __WW_MUTEX_INITIALIZER(mutexname, ww_class) @@ -123,6 +132,8 @@ static inline void ww_acquire_init(struct ww_acquire_ctx *ctx, ctx->task = current; ctx->stamp = atomic_long_inc_return_relaxed(&ww_class->stamp); ctx->acquired = 0; + ctx->wounded = false; + ctx->is_wait_die = ww_class->is_wait_die; #ifdef CONFIG_DEBUG_MUTEXES ctx->ww_class = ww_class; ctx->done_acquire = 0; diff --git a/kernel/locking/locktorture.c b/kernel/locking/locktorture.c index 6850ffd69125..907e0325892c 100644 --- a/kernel/locking/locktorture.c +++ b/kernel/locking/locktorture.c @@ -365,7 +365,7 @@ static struct lock_torture_ops mutex_lock_ops = { }; #include -static DEFINE_WW_CLASS(torture_ww_class); +static DEFINE_WD_CLASS(torture_ww_class); static DEFINE_WW_MUTEX(torture_ww_mutex_0, &torture_ww_class); static DEFINE_WW_MUTEX(torture_ww_mutex_1, &torture_ww_class); static DEFINE_WW_MUTEX(torture_ww_mutex_2, &torture_ww_class); diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 412b4fc08235..8ca83a5e3d24 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -172,6 +172,21 @@ static inline bool __mutex_waiter_is_first(struct mutex *lock, struct mutex_wait return list_first_entry(&lock->wait_list, struct mutex_waiter, list) == waiter; } +/* + * Add @waiter to a given location in the lock wait_list and set the + * FLAG_WAITERS flag if it's the first waiter. + */ +static void __sched +__mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter, + struct list_head *list) +{ + debug_mutex_add_waiter(lock, waiter, current); + + list_add_tail(&waiter->list, list); + if (__mutex_waiter_is_first(lock, waiter)) + __mutex_set_flag(lock, MUTEX_FLAG_WAITERS); +} + /* * Give up ownership to a specific task, when @task = NULL, this is equivalent * to a regular unlock. Sets PICKUP on a handoff, clears HANDOF, preserves @@ -248,6 +263,11 @@ EXPORT_SYMBOL(mutex_lock); * The newer transactions are killed when: * It (the new transaction) makes a request for a lock being held * by an older transaction. + * + * Wound-Wait: + * The newer transactions are wounded when: + * An older transaction makes a request for a lock being held by + * the newer transaction. */ /* @@ -319,6 +339,9 @@ static bool __sched __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter, struct ww_acquire_ctx *ww_ctx) { + if (!ww_ctx->is_wait_die) + return false; + if (waiter->ww_ctx->acquired > 0 && __ww_ctx_stamp_after(waiter->ww_ctx, ww_ctx)) { debug_mutex_wake_waiter(lock, waiter); @@ -328,13 +351,65 @@ __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter, return true; } +/* + * Wound-Wait; wound a younger @hold_ctx if it holds the lock. + * + * Wound the lock holder if there are waiters with older transactions than + * the lock holders. Even if multiple waiters may wound the lock holder, + * it's sufficient that only one does. + */ +static bool __ww_mutex_wound(struct mutex *lock, + struct ww_acquire_ctx *ww_ctx, + struct ww_acquire_ctx *hold_ctx) +{ + struct task_struct *owner = __mutex_owner(lock); + + lockdep_assert_held(&lock->wait_lock); + + /* + * Possible through __ww_mutex_add_waiter() when we race with + * ww_mutex_set_context_fastpath(). In that case we'll get here again + * through __ww_mutex_check_waiters(). + */ + if (!hold_ctx) + return false; + + /* + * Can have !owner because of __mutex_unlock_slowpath(), but if owner, + * it cannot go away because we'll have FLAG_WAITERS set and hold + * wait_lock. + */ + if (!owner) + return false; + + if (ww_ctx->acquired > 0 && __ww_ctx_stamp_after(hold_ctx, ww_ctx)) { + hold_ctx->wounded = 1; + + /* + * wake_up_process() paired with set_current_state() + * inserts sufficient barriers to make sure @owner either sees + * it's wounded in __ww_mutex_lock_check_stamp() or has a + * wakeup pending to re-read the wounded state. + */ + if (owner != current) + wake_up_process(owner); + + return true; + } + + return false; +} + /* * We just acquired @lock under @ww_ctx, if there are later contexts waiting - * behind us on the wait-list, check if they need to die. + * behind us on the wait-list, check if they need to die, or wound us. * * See __ww_mutex_add_waiter() for the list-order construction; basically the * list is ordered by stamp, smallest (oldest) first. * + * This relies on never mixing wait-die/wound-wait on the same wait-list; + * which is currently ensured by that being a ww_class property. + * * The current task must not be on the wait list. */ static void __sched @@ -348,7 +423,8 @@ __ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) if (!cur->ww_ctx) continue; - if (__ww_mutex_die(lock, cur, ww_ctx)) + if (__ww_mutex_die(lock, cur, ww_ctx) || + __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx)) break; } } @@ -369,17 +445,23 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) * and keep spinning, or it will acquire wait_lock, add itself * to waiter list and sleep. */ - smp_mb(); /* ^^^ */ + smp_mb(); /* See comments above and below. */ /* - * Check if lock is contended, if not there is nobody to wake up + * [W] ww->ctx = ctx [W] MUTEX_FLAG_WAITERS + * MB MB + * [R] MUTEX_FLAG_WAITERS [R] ww->ctx + * + * The memory barrier above pairs with the memory barrier in + * __ww_mutex_add_waiter() and makes sure we either observe ww->ctx + * and/or !empty list. */ if (likely(!(atomic_long_read(&lock->base.owner) & MUTEX_FLAG_WAITERS))) return; /* * Uh oh, we raced in fastpath, check if any of the waiters need to - * die. + * die or wound us. */ spin_lock(&lock->base.wait_lock); __ww_mutex_check_waiters(&lock->base, ctx); @@ -681,7 +763,9 @@ __ww_mutex_kill(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) /* - * Check whether we need to kill the transaction for the current lock acquire. + * Check the wound condition for the current lock acquire. + * + * Wound-Wait: If we're wounded, kill ourself. * * Wait-Die: If we're trying to acquire a lock already held by an older * context, kill ourselves. @@ -700,6 +784,13 @@ __ww_mutex_check_kill(struct mutex *lock, struct mutex_waiter *waiter, if (ctx->acquired == 0) return 0; + if (!ctx->is_wait_die) { + if (ctx->wounded) + return __ww_mutex_kill(lock, ctx); + + return 0; + } + if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx)) return __ww_mutex_kill(lock, ctx); @@ -726,7 +817,8 @@ __ww_mutex_check_kill(struct mutex *lock, struct mutex_waiter *waiter, * Waiters without context are interspersed in FIFO order. * * Furthermore, for Wait-Die kill ourself immediately when possible (there are - * older contexts already waiting) to avoid unnecessary waiting. + * older contexts already waiting) to avoid unnecessary waiting and for + * Wound-Wait ensure we wound the owning context when it is younger. */ static inline int __sched __ww_mutex_add_waiter(struct mutex_waiter *waiter, @@ -735,16 +827,21 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, { struct mutex_waiter *cur; struct list_head *pos; + bool is_wait_die; if (!ww_ctx) { - list_add_tail(&waiter->list, &lock->wait_list); + __mutex_add_waiter(lock, waiter, &lock->wait_list); return 0; } + is_wait_die = ww_ctx->is_wait_die; + /* * Add the waiter before the first waiter with a higher stamp. * Waiters without a context are skipped to avoid starving - * them. Wait-Die waiters may die here. + * them. Wait-Die waiters may die here. Wound-Wait waiters + * never die here, but they are sorted in stamp order and + * may wound the lock holder. */ pos = &lock->wait_list; list_for_each_entry_reverse(cur, &lock->wait_list, list) { @@ -757,10 +854,12 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, * is no point in queueing behind it, as we'd have to * die the moment it would acquire the lock. */ - int ret = __ww_mutex_kill(lock, ww_ctx); + if (is_wait_die) { + int ret = __ww_mutex_kill(lock, ww_ctx); - if (ret) - return ret; + if (ret) + return ret; + } break; } @@ -771,7 +870,23 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, __ww_mutex_die(lock, cur, ww_ctx); } - list_add_tail(&waiter->list, pos); + __mutex_add_waiter(lock, waiter, pos); + + /* + * Wound-Wait: if we're blocking on a mutex owned by a younger context, + * wound that such that we might proceed. + */ + if (!is_wait_die) { + struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); + + /* + * See ww_mutex_set_context_fastpath(). Orders setting + * MUTEX_FLAG_WAITERS vs the ww->ctx load, + * such that either we or the fastpath will wound @ww->ctx. + */ + smp_mb(); + __ww_mutex_wound(lock, ww_ctx, ww->ctx); + } return 0; } @@ -795,6 +910,14 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, if (use_ww_ctx && ww_ctx) { if (unlikely(ww_ctx == READ_ONCE(ww->ctx))) return -EALREADY; + + /* + * Reset the wounded flag after a kill. No other process can + * race and wound us here since they can't have a valid owner + * pointer if we don't have any locks held. + */ + if (ww_ctx->acquired == 0) + ww_ctx->wounded = 0; } preempt_disable(); @@ -828,7 +951,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, if (!use_ww_ctx) { /* add waiting tasks to the end of the waitqueue (FIFO): */ - list_add_tail(&waiter.list, &lock->wait_list); + __mutex_add_waiter(lock, &waiter, &lock->wait_list); + #ifdef CONFIG_DEBUG_MUTEXES waiter.ww_ctx = MUTEX_POISON_WW_CTX; @@ -847,9 +971,6 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, waiter.task = current; - if (__mutex_waiter_is_first(lock, &waiter)) - __mutex_set_flag(lock, MUTEX_FLAG_WAITERS); - set_current_state(state); for (;;) { /* @@ -906,6 +1027,16 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, acquired: __set_current_state(TASK_RUNNING); + if (use_ww_ctx && ww_ctx) { + /* + * Wound-Wait; we stole the lock (!first_waiter), check the + * waiters as anyone might want to wound us. + */ + if (!ww_ctx->is_wait_die && + !__mutex_waiter_is_first(lock, &waiter)) + __ww_mutex_check_waiters(lock, ww_ctx); + } + mutex_remove_waiter(lock, &waiter, current); if (likely(list_empty(&lock->wait_list))) __mutex_clear_flag(lock, MUTEX_FLAGS); diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c index 0e4cd64ad2c0..5b915b370d5a 100644 --- a/kernel/locking/test-ww_mutex.c +++ b/kernel/locking/test-ww_mutex.c @@ -26,7 +26,7 @@ #include #include -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WD_CLASS(ww_class); struct workqueue_struct *wq; struct test_mutex { diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index b5c1293ce147..1e1bbf171eca 100644 --- a/lib/locking-selftest.c +++ b/lib/locking-selftest.c @@ -29,7 +29,7 @@ */ static unsigned int debug_locks_verbose; -static DEFINE_WW_CLASS(ww_lockdep); +static DEFINE_WD_CLASS(ww_lockdep); static int __init setup_debug_locks_verbose(char *str) { -- 2.14.3