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 19EB17DF88 for ; Wed, 13 Jun 2018 07:49:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754538AbeFMHsq (ORCPT ); Wed, 13 Jun 2018 03:48:46 -0400 Received: from mail-eopbgr720071.outbound.protection.outlook.com ([40.107.72.71]:65056 "EHLO NAM05-CO1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S934508AbeFMHsl (ORCPT ); Wed, 13 Jun 2018 03:48:41 -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=ciWhR1bsE4PGajszOpEctfkJsKOSNlEIO9jnT3dqm3o=; b=jp4Z+ei2B1dH/QS/R/KUvIBP7dCHMf+NlsuI/HYbkIor140xHpdL/k+r7r8yPHo0HHfBpvw3yBwwcUISgn+q+Wxaj1nejNucX/Xf+T2L63ERMjdMAawkQPHRHCdIzZElSB8Kys0fjN7J863BHNxQoybQeblJuuNhYAevLzD6gz4= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=thellstrom@vmware.com; Received: from localhost.localdomain (155.4.205.56) by SN6PR05MB4589.namprd05.prod.outlook.com (2603:10b6:805:38::23) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.863.6; Wed, 13 Jun 2018 07:48:32 +0000 From: Thomas Hellstrom To: dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org Cc: Thomas Hellstrom , Peter Zijlstra , 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 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes Date: Wed, 13 Jun 2018 09:47:44 +0200 Message-Id: <20180613074745.14750-2-thellstrom@vmware.com> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180613074745.14750-1-thellstrom@vmware.com> References: <20180613074745.14750-1-thellstrom@vmware.com> MIME-Version: 1.0 Content-Type: text/plain X-Originating-IP: [155.4.205.56] X-ClientProxiedBy: HE1PR0402CA0057.eurprd04.prod.outlook.com (2603:10a6:7:7c::46) To SN6PR05MB4589.namprd05.prod.outlook.com (2603:10b6:805:38::23) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 33643625-2d42-4ee6-b8b8-08d5d10211cb X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:(7020095)(4652020)(5600026)(711020)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020);SRVR:SN6PR05MB4589; X-Microsoft-Exchange-Diagnostics: 1;SN6PR05MB4589;3:E7RqlVl8HgTpGE9pRBsvkxkQx3k40HTXY+REMJHNYvLhQB82pcwDXyJRJxrrT6FsCmzZxDGMSqSb3MqrYVTXb1RwLto0Yi3GpJ41GZSW67ntN3XXUFLvHWc4cQUsiC5uYjXd+zboiBRvOBRnzjnSl9GyoSJPNc3vRZqWqaS7NPQ74/XaTlhQFsIX5PG+ABDb5g6wn5XKoslTq0fTCL71RnuJhFw8IMRD4/yPz2WajIoMlcHJSNpNCM61QQ7xsanH;25:eDtsOWvWgqndM84TMEr2WT/pLZmYXdDsh3Ae56PCwYPHLQrc7zpIVe6La0iPimeBmU7Jsp6lyLAoZVJ4XFUL+Ixwe/F5SVj9151HhuC/NBy/pYTY71bwNxEqo46qeoh9L6aZGTsUvKgP9xIQA2R1FxQ6g16zE5TvCE4ihuvo+7McdnuBYMUsG+Eiqz5SwkC3lX09gaW1WkYt03+qesrm6olHCYJTabLlMRRXhjjQBsPwZjkPCesEfuLnSSf/Zfh5v2qOcez5gYSDL89HdZCVBiRi/Kdt7gZjw9kKgRG/s41QjLjFJG05I6L82CwJ/dz0TfphCFLQ4yDjqWE8iyK9gg==;31:YZ2imemwOnRb3ENBsGeNUYgv3xjg2EgiQCpMB9gIZrJxD0QO6ty+ui/TxvNjofRwj2AZMdIQYmlztXHExMUCpxfxaSTrNTFsiALtkpXczxIwgSlIXxNiPmBStiEsKdOS2IeTBw934J6Lo7OI41e2J/q9OgcEosEcc2pJu3mN81zumAik8b2Z3LK1ju8F99LGeVlO5JmvfRKcy/cwvf8D8bmY3W82kURK9hPkT0jms6E= X-MS-TrafficTypeDiagnostic: SN6PR05MB4589: X-Microsoft-Exchange-Diagnostics: 1;SN6PR05MB4589;20:fbK/x9VHpJd7aoXtyA00901oidesEZsnZB73Ognw+QmQmZsP/ieSrHFia4JXPPALP5+lLqRlIpt9b5rKmv2AJHpMUMC92DFRVfwuU3vTMhALnn/wwK138KZv3w1+Ib02fouE3rqnJKhzlfsC8QT1HS0/UybAF6wOq6cUMCRqbphND7N3fB0cYoOctfIo8jhEku8DlK9ogWHlqQ4iQxuQlcOZf/ZmHyw0ccOobXfdgb9oYfDeLXe/i6htkumS7hLHre8ZY/iUH863SYN0sGSBaWcuSQWGZRutzKgQS4JZFKPI791bqhWb/t9edD14kOGHUUQ2elhqnk0T5iWIgg/hq874Abw2ivb+Q2dRKYvN+chDvOeJH0ACux5S93p8rMJrEW07ARExaJ76Fk6iQyY+lon2DH34Y83kgVOBL4pctrM2hVqlddsYH9vS4Dfim5G3Hk1LERW9ARiBqkM0EjZB0lR0GWGriLSIbceIRcmA8bCWAPcUnI8l8ma+Ip9T0uy7 X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(61668805478150)(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)(3231254)(944501410)(52105095)(10201501046)(93006095)(93001095)(3002001)(149027)(150027)(6041310)(20161123562045)(20161123564045)(20161123558120)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(6072148)(201708071742011)(7699016);SRVR:SN6PR05MB4589;BCL:0;PCL:0;RULEID:;SRVR:SN6PR05MB4589; X-Microsoft-Exchange-Diagnostics: 1;SN6PR05MB4589;4:I7+xOpDSvmf0aoBfhOtvqhir0CIwfsQ+8R8gGBsj0sTGMu83J4ANK+rBUJtn/4CJsFHbhF+Ii5Eva1H3r5CF+M+QJ2/JGRJWoX1kKqMWFAQqkpz7CEQ3H+xblJIXk/82eomJHcf6/287evxTc7tIPBYPeXExH0R/BnhDHQjzEaBgPlKd7tk4P8w7e6ogwE1jEKfgp5W+/bt76ajnb+cx+Edz/5BxeamEg0gSuzYEficevZEo69djl3DFOcWCpttftlLkbdqJQMvUv4G4h90gLRncdf1SfuBldA8PICKp6bj1Z/oazRSG8xW/gKqtQy3OYLYxS76k5DjsZLmGZpeLK6Mt/5gzqUGYwTscy6J8fJE8s16JRKcESnwf1Mn5osjrF2d2R8cPfvmhCDyLgeBeThMvQb776D6dq1pfDeY8SaR4Fm31DV6Z8Wh6uhJKFkdy X-Forefront-PRVS: 07025866F6 X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10009020)(6069001)(39860400002)(346002)(39380400002)(396003)(376002)(366004)(199004)(189003)(81156014)(25786009)(476003)(186003)(551934003)(16526019)(478600001)(486006)(6666003)(2906002)(106356001)(48376002)(50466002)(53936002)(8676002)(81166006)(8936002)(305945005)(6512007)(7736002)(26005)(956004)(2616005)(6486002)(5660300001)(59450400001)(316002)(6506007)(105586002)(386003)(4326008)(11346002)(446003)(51416003)(76176011)(7416002)(52116002)(16586007)(54906003)(36756003)(97736004)(47776003)(1076002)(3846002)(6116002)(50226002)(66066001)(68736007)(86362001);DIR:OUT;SFP:1101;SCL:1;SRVR:SN6PR05MB4589;H:localhost.localdomain;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;SN6PR05MB4589;23:NHrnbrTc0pRQhE2iTDQHmdDcA10pB1KtFQeBiGbPL?= =?us-ascii?Q?LOkf7QO9hVbl7NjpaFWOhdoH66nz2EgSQTyYT3Ke04IB6wTPl51xZYNBXP2J?= =?us-ascii?Q?B4i/GPAPYmgIS1yMFNUM8C5lLp35TavETdhK5xyBonQO9aKNy6wBQYYcdGXm?= =?us-ascii?Q?tPsrq1rlWNjgwpjWGNyzmkY/F43abyIhp8zr1RGchYRIVQQgu0w/LHZthes3?= =?us-ascii?Q?yeIAC7P4kuoxpQ4h4Ujrp2uYMdJB5Km3R7ANSc08vHblKxIR6C/r8HqqQd91?= =?us-ascii?Q?qQ/wXb/oyAMXCNvKz7p6spd2YWWq7647bgzrFqWhwNvTidhCvg6dzAvQZolz?= =?us-ascii?Q?r/4ou1fSM59YlAmqGuG7o5RtlHcb0QOGGDrlz7nZ/O6T6lWGYsfiMwPejnQx?= =?us-ascii?Q?/WXq4BBtIC0Z9tJOQ02LEdai/No10LJRPfUIvcn9r/pedWyNNlcxMzqbNi71?= =?us-ascii?Q?+pFOo6nxpcn/jgsfFwmv6UPx2rc0TPHNFojiC6ISJSwoQoGyE/rtHUfwhpho?= =?us-ascii?Q?4F8lecT8e0zwjHOdrxXlKOj1dTJDr1OzSoJwpzvucEBiyUXn2hoKinIY6Sjh?= =?us-ascii?Q?4HJbneId+ddQjwqUpeGQlkDejUyeMeLTNk0NjfYT5aH7lWrf5C+k/G8ehPuh?= =?us-ascii?Q?t57xSHUfIsbqOnX7+FB+NkZGW5CKLJymfsg2wBb44idSytmP0VZCvCi/7eZN?= =?us-ascii?Q?/X4IlFiEvT5UH8U4ptiL6gUFphDv17v0/IQPvrBt7CAiFFC1HLBi3l6mBO2O?= =?us-ascii?Q?J5GOKMsvQr+o6eOohuB6njOfLMevUz2eQg+dgZbeEoy9XP6MZ4QEGVI23VQA?= =?us-ascii?Q?XbuQ4edhKTaof5bTn6DTXuKE2pWPiSZHsIGrrOp/kZ0Hyiue6LDgZ2sDTgL+?= =?us-ascii?Q?XfgbqAfoH+WxXPshBMim8NLsZSG+9GZRUjDP/00kF1/Ah0aSFqfufT/f9lXX?= =?us-ascii?Q?S3Vd03zD13Y71J6Uu5Wc9VPxN5j9enYQ/p8IBB8uef5/29k8mGAWv1YE/l1S?= =?us-ascii?Q?rrKg6QzBrCQM/ILwid5oSL+dd6+/XvAcEf/nSUCETcf0g7N0uz/86pBcjhx1?= =?us-ascii?Q?b0zSLNhQJBrzcZNqTK+C4TCCauSfxUc+dmVk0Bh6IWp8taI+YAXh4m+IAwQM?= =?us-ascii?Q?zT+hR50VhA+DkIr74yh0Is6Q+SxTPR+ZxIoWh/ofHdO7zRfEd78eA7L58grJ?= =?us-ascii?Q?14PTDa8Pub+2UC5WckS5CkGzKi32L1aEr5JNp1Ch2sZBlZA/YrGWmM5XfYaP?= =?us-ascii?Q?nUPOjDu8kjfRiWO/HgCS7TJt3Ir7RlLZr3jhN5Jrg0jewXh3YlVN7AGT96XS?= =?us-ascii?B?dz09?= X-Microsoft-Antispam-Message-Info: zmEmolCAKRcZJKFnpcGsdVAA+5kTMVmuDxEq1Br3S9KTsArywl9lLz+xDOM5vwPG4f7moppxTxKa559KoPmpmFZv7M9J+PFeqU5GeRzbFIUYpEnRK53fT1BTz66cW4hKOhSI3zaeMoXch/U/UnlGIFBum26cy8YSIr6aciB1Ci7WtpEv9u1b/8xwYA7bnK2b X-Microsoft-Exchange-Diagnostics: 1;SN6PR05MB4589;6:2dDyMfTL7cuo/Fb/UZ/86qxd611aAixVYDKJaJZ1lFx4SSB68onLNkyLWnr/lnP43IGZrfPOdwx1QVu1IE1tXjA/aATg5zhXoTIweQ4NriGRcxNOPl7Jumk30mi5UhSt4SH4C/XzVUfUcx1MxsxNZ03fDb+VHSWMeoUJoXVgbofFZjmDH7McMxaxAEy2MtfBcM/xUD8VdFdQwSf6TEsL77GDztK7FrJhc+rWTZ5xzIS7scKs7YuPuNxuPHLzAReB/cU2WIG1vNCsxXAJ32HFsWjmaroisnP7wp1PmC2dYxus99o164ZSpnP9ArPWlIhuXswADmlnYlmEBFw87me0IfT20bQZZjuYPCD0IyRvH5GROEp4Rvs4WcTAvglRDo/LcPD+nhCENazkWFrG1f+1UDe/QYd8tRn+feV0pdnHEptbo+ZXJW1qyVhLt2AeLwXsaplwFE5gd1LhpJVELoJE/g==;5:iRUcpqxSBnXzSybV7VsxknPBcgVc5dRhH08kG5f9vL3Q/kp1wJJhzJjEse7cN8Hlb6qkiudNdWU1pmr7IknJkFsB4rUmG5zFY03OIhybs8fd5VyoMyko5YlmIGFbqEzQ22oERUZl9kHpYtUzsSxLfvboUgrMWykA7V9xmQgiftE=;24:ov4lTwGdoADvEsEuFef/KzMdFI4MCGMZHbK9OY0oOGf3LYneIo3qr78Q8R87o9AoNTos0l9wGt86DXmBr9TToHybgMuI0s0a2KKhj//kLlY= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1;SN6PR05MB4589;7:BMTi+xMq3pqeVSCy80dd3H4uXh4NVdnQjiL7E60zcK3hh8wg1XQG/A6MUyZ6RN9hlHAUmFFHIp1qZ9a8KSc05sqbhPTiMRxLRKGy3wmyicL6omUTOWkU11TXofe4pEi9bQiQ+Si93bqWjuEPdrX1k+mvDAvXRAr6nbDvpQdlzQezSbx/PvtyiLOsyV2kQIP0o1iIiaGePOQPDuDM0QIxwr9PKfGKgMDsekGHAKN4Agp06sodWP7Mafr0tj96n2VQ;20:IzPI1woiT2/SByMkSSVGBWtqkdpMdBB7AFUXigfyZJg87/GMmot8LGtSL2z+tYm3sVbr8iR+JzypDZ7XGiO4N3xSV72hP/ooBl+jb2921Drk8+PlR8afRumlKAzbLRJVnrbZcbT0yx5kf3iwBsUBP4xLGvrTDbYyM1ixykqv/WI= X-OriginatorOrg: vmware.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Jun 2018 07:48:32.2589 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 33643625-2d42-4ee6-b8b8-08d5d10211cb X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: b39138ca-3cee-4b4a-a4d6-cd83d9dd62f0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR05MB4589 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-04 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: Peter Zijlstra 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 Signed-off-by: Thomas Hellstrom --- 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 | 19 ++++-- kernel/locking/locktorture.c | 2 +- kernel/locking/mutex.c | 98 ++++++++++++++++++++++++++++--- kernel/locking/test-ww_mutex.c | 2 +- lib/locking-selftest.c | 2 +- 8 files changed, 152 insertions(+), 32 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 34c3a1b50b9a..29c85623b551 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,23 @@ 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/wound: -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 is wounded. +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 +preempts the transaction holding the lock, requiring it to back off. It +Wounds the other transaction. +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 which requires a reliable way to preempt another transaction. Concepts -------- @@ -47,10 +60,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,10 +105,15 @@ provided. Usage ----- +The algorithm (Wait-Die vs Wound-Wait) is chosen using the _is_wait_die +argument to DEFINE_WW_CLASS(). As a rough rule of thumb, use Wound-Wait iff you +typically expect the number of simultaneous competing transactions to be small, +and the rollback cost can be substantial. + Three different ways to acquire locks within the same w/w class. Common definitions for methods #1 and #2: -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WW_CLASS(ww_class, false); struct obj { struct ww_mutex lock; @@ -243,7 +263,7 @@ struct obj { struct list_head locked_list; }; -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WW_CLASS(ww_class, false); void __unlock_objs(struct list_head *list) { @@ -312,12 +332,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..039571b9fea1 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_WW_CLASS(reservation_ww_class, true); 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..f22a7ef41de1 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_WW_CLASS(crtc_ww_class, true); /** * drm_modeset_lock_all - take all modeset locks diff --git a/include/linux/ww_mutex.h b/include/linux/ww_mutex.h index 39fda195bf78..6278077f288b 100644 --- a/include/linux/ww_mutex.h +++ b/include/linux/ww_mutex.h @@ -8,6 +8,8 @@ * * Wound/wait 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,15 +25,17 @@ struct ww_class { struct lock_class_key mutex_key; const char *acquire_name; const char *mutex_name; + bool is_wait_die; }; struct ww_acquire_ctx { struct task_struct *task; unsigned long stamp; unsigned acquired; + bool wounded; + struct ww_class *ww_class; #ifdef CONFIG_DEBUG_MUTEXES unsigned done_acquire; - struct ww_class *ww_class; struct ww_mutex *contending_lock; #endif #ifdef CONFIG_DEBUG_LOCK_ALLOC @@ -58,17 +62,19 @@ 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_WW_CLASS(classname) \ - struct ww_class classname = __WW_CLASS_INITIALIZER(classname) +#define DEFINE_WW_CLASS(classname, _is_wait_die) \ + struct ww_class classname = __WW_CLASS_INITIALIZER(classname, \ + _is_wait_die) #define DEFINE_WW_MUTEX(mutexname, ww_class) \ struct ww_mutex mutexname = __WW_MUTEX_INITIALIZER(mutexname, ww_class) @@ -123,8 +129,9 @@ 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; -#ifdef CONFIG_DEBUG_MUTEXES ctx->ww_class = ww_class; + ctx->wounded = false; +#ifdef CONFIG_DEBUG_MUTEXES ctx->done_acquire = 0; ctx->contending_lock = NULL; #endif diff --git a/kernel/locking/locktorture.c b/kernel/locking/locktorture.c index 6850ffd69125..778ed026382f 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_WW_CLASS(torture_ww_class, true); 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 2048359f33d2..b449a012c6f9 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -290,12 +290,47 @@ __ww_ctx_stamp_after(struct ww_acquire_ctx *a, struct ww_acquire_ctx *b) (a->stamp != b->stamp || a > b); } +/* + * Wound the lock holder transaction if it's younger than the contending + * transaction, and there is a possibility of a deadlock. + * Also if the lock holder transaction isn't the current transaction, + * Make sure it's woken up in case it's sleeping on another ww mutex. + */ +static bool __ww_mutex_wound(struct mutex *lock, + struct ww_acquire_ctx *ww_ctx, + struct ww_acquire_ctx *hold_ctx) +{ + struct task_struct *owner = + __owner_task(atomic_long_read(&lock->owner)); + + lockdep_assert_held(&lock->wait_lock); + + if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) && + ww_ctx->acquired > 0) { + WRITE_ONCE(hold_ctx->wounded, true); + if (owner != current) { + /* + * wake_up_process() inserts a write memory barrier to + * make sure owner sees it is wounded before + * TASK_RUNNING in case it's sleeping on another + * ww_mutex. Note that owner points to a valid + * task_struct as long as we hold the wait_lock. + */ + wake_up_process(owner); + } + return true; + } + + return false; +} + /* * Wake up any waiters that may have to back off when the lock is held by the * given context. * * Due to the invariants on the wait list, this can only affect the first - * waiter with a context. + * waiter with a context, unless the Wound-Wait algorithm is used where + * also subsequent waiters with a context main wound the lock holder. * * The current task must not be on the wait list. */ @@ -303,6 +338,7 @@ static void __sched __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) { struct mutex_waiter *cur; + bool is_wait_die = ww_ctx->ww_class->is_wait_die; lockdep_assert_held(&lock->wait_lock); @@ -310,13 +346,14 @@ __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) if (!cur->ww_ctx) continue; - if (cur->ww_ctx->acquired > 0 && + if (is_wait_die && cur->ww_ctx->acquired > 0 && __ww_ctx_stamp_after(cur->ww_ctx, ww_ctx)) { debug_mutex_wake_waiter(lock, cur); wake_up_process(cur->task); } - break; + if (is_wait_die || __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx)) + break; } } @@ -338,12 +375,17 @@ 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 + * Check if lock is contended, if not there is nobody to wake up. + * Checking MUTEX_FLAG_WAITERS is not enough here, since we need to + * order against the lock->ctx check in __ww_mutex_wound called from + * __ww_mutex_add_waiter. We can use list_empty without taking the + * wait_lock, given the memory barrier above and the list_empty + * documentation. */ - if (likely(!(atomic_long_read(&lock->base.owner) & MUTEX_FLAG_WAITERS))) + if (likely(list_empty(&lock->base.wait_list))) return; /* @@ -653,6 +695,17 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct mutex_waiter *waiter, struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx); struct mutex_waiter *cur; + /* + * If we miss a wounded == true here, we will have a pending + * TASK_RUNNING and pick it up on the next schedule fall-through. + */ + if (!ctx->ww_class->is_wait_die) { + if (READ_ONCE(ctx->wounded)) + goto deadlock; + else + return 0; + } + if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx)) goto deadlock; @@ -683,12 +736,15 @@ __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); return 0; } + is_wait_die = ww_ctx->ww_class->is_wait_die; + /* * Add the waiter before the first waiter with a higher stamp. * Waiters without a context are skipped to avoid starving @@ -701,7 +757,7 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, if (__ww_ctx_stamp_after(ww_ctx, cur->ww_ctx)) { /* Back off immediately if necessary. */ - if (ww_ctx->acquired > 0) { + if (is_wait_die && ww_ctx->acquired > 0) { #ifdef CONFIG_DEBUG_MUTEXES struct ww_mutex *ww; @@ -721,13 +777,26 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, * Wake up the waiter so that it gets a chance to back * off. */ - if (cur->ww_ctx->acquired > 0) { + if (is_wait_die && cur->ww_ctx->acquired > 0) { debug_mutex_wake_waiter(lock, cur); wake_up_process(cur->task); } } list_add_tail(&waiter->list, pos); + if (!is_wait_die) { + struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); + + /* + * Make sure a racing lock taker sees a non-empty waiting list + * before we read ww->ctx, so that if we miss ww->ctx, the + * racing lock taker will call __ww_mutex_wake_up_for_backoff() + * and wound itself. + */ + smp_mb(); + __ww_mutex_wound(lock, ww_ctx, ww->ctx); + } + return 0; } @@ -750,6 +819,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 backoff. + * No other process can race and wound us here since they + * can't have a valid owner pointer at this time + */ + if (ww_ctx->acquired == 0) + ww_ctx->wounded = false; } preempt_disable(); @@ -858,6 +935,11 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, acquired: __set_current_state(TASK_RUNNING); + /* We stole the lock. Need to check wounded status. */ + if (use_ww_ctx && ww_ctx && !ww_ctx->ww_class->is_wait_die && + !__mutex_waiter_is_first(lock, &waiter)) + __ww_mutex_wakeup_for_backoff(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..c7fc112d691d 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_WW_CLASS(ww_class, true); struct workqueue_struct *wq; struct test_mutex { diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index b5c1293ce147..e52065f2acbf 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_WW_CLASS(ww_lockdep, true); 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 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes Date: Wed, 13 Jun 2018 09:47:44 +0200 Message-ID: <20180613074745.14750-2-thellstrom@vmware.com> References: <20180613074745.14750-1-thellstrom@vmware.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Return-path: Received: from NAM05-CO1-obe.outbound.protection.outlook.com (mail-eopbgr720070.outbound.protection.outlook.com [40.107.72.70]) by gabe.freedesktop.org (Postfix) with ESMTPS id CA6ED6E600 for ; Wed, 13 Jun 2018 07:48:39 +0000 (UTC) In-Reply-To: <20180613074745.14750-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 Cc: Kate Stewart , Thomas Hellstrom , Davidlohr Bueso , Jonathan Corbet , Peter Zijlstra , linux-doc@vger.kernel.org, Josh Triplett , linaro-mm-sig@lists.linaro.org, David Airlie , Greg Kroah-Hartman , Ingo Molnar , 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 dGVzdAp0YWcgcGF0Y2gtMTgtMDYtMDQKCkVhY2ggdGhyZWFkIHJ1bnMgMTAwMDAwIGJhdGNoZXMg b2YgbG9jayAvIHVubG9jayA4MDAgd3cgbXV0ZXhlcyByYW5kb21seQpjaG9zZW4gb3V0IG9mIDEw MDAwMC4gRm91ciBjb3JlIEludGVsIHg4Nl82NDoKCkFsZ29yaXRobSAgICAjdGhyZWFkcyAgICAg ICBSb2xsYmFja3MgIHRpbWUKV291bmQtV2FpdCAgIDQgICAgICAgICAgICAgIH4xMDAgICAgICAg fjE3cy4KV2FpdC1EaWUgICAgIDQgICAgICAgICAgICAgIH4xNTAwMDAgICAgfjE5cy4KV291bmQt V2FpdCAgIDE2ICAgICAgICAgICAgIH4zNjAwMDAgICAgfjEwOXMuCldhaXQtRGllICAgICAxNiAg ICAgICAgICAgICB+NDUwMDAwICAgIH44MnMuCgpDYzogUGV0ZXIgWmlqbHN0cmEgPHBldGVyekBp bmZyYWRlYWQub3JnPgpDYzogSW5nbyBNb2xuYXIgPG1pbmdvQHJlZGhhdC5jb20+CkNjOiBKb25h dGhhbiBDb3JiZXQgPGNvcmJldEBsd24ubmV0PgpDYzogR3VzdGF2byBQYWRvdmFuIDxndXN0YXZv QHBhZG92YW4ub3JnPgpDYzogTWFhcnRlbiBMYW5raG9yc3QgPG1hYXJ0ZW4ubGFua2hvcnN0QGxp bnV4LmludGVsLmNvbT4KQ2M6IFNlYW4gUGF1bCA8c2VhbnBhdWxAY2hyb21pdW0ub3JnPgpDYzog RGF2aWQgQWlybGllIDxhaXJsaWVkQGxpbnV4LmllPgpDYzogRGF2aWRsb2hyIEJ1ZXNvIDxkYXZl QHN0Z29sYWJzLm5ldD4KQ2M6ICJQYXVsIEUuIE1jS2VubmV5IiA8cGF1bG1ja0BsaW51eC52bmV0 LmlibS5jb20+CkNjOiBKb3NoIFRyaXBsZXR0IDxqb3NoQGpvc2h0cmlwbGV0dC5vcmc+CkNjOiBU aG9tYXMgR2xlaXhuZXIgPHRnbHhAbGludXRyb25peC5kZT4KQ2M6IEthdGUgU3Rld2FydCA8a3N0 ZXdhcnRAbGludXhmb3VuZGF0aW9uLm9yZz4KQ2M6IFBoaWxpcHBlIE9tYnJlZGFubmUgPHBvbWJy ZWRhbm5lQG5leGIuY29tPgpDYzogR3JlZyBLcm9haC1IYXJ0bWFuIDxncmVna2hAbGludXhmb3Vu ZGF0aW9uLm9yZz4KQ2M6IGxpbnV4LWRvY0B2Z2VyLmtlcm5lbC5vcmcKQ2M6IGxpbnV4LW1lZGlh QHZnZXIua2VybmVsLm9yZwpDYzogbGluYXJvLW1tLXNpZ0BsaXN0cy5saW5hcm8ub3JnClNpZ25l ZC1vZmYtYnk6IFRob21hcyBIZWxsc3Ryb20gPHRoZWxsc3Ryb21Adm13YXJlLmNvbT4KLS0tCiBE b2N1bWVudGF0aW9uL2xvY2tpbmcvd3ctbXV0ZXgtZGVzaWduLnR4dCB8IDU3ICsrKysrKysrKysr KysrLS0tLQogZHJpdmVycy9kbWEtYnVmL3Jlc2VydmF0aW9uLmMgICAgICAgICAgICAgfCAgMiAr LQogZHJpdmVycy9ncHUvZHJtL2RybV9tb2Rlc2V0X2xvY2suYyAgICAgICAgfCAgMiArLQogaW5j bHVkZS9saW51eC93d19tdXRleC5oICAgICAgICAgICAgICAgICAgfCAxOSArKysrLS0KIGtlcm5l bC9sb2NraW5nL2xvY2t0b3J0dXJlLmMgICAgICAgICAgICAgIHwgIDIgKy0KIGtlcm5lbC9sb2Nr aW5nL211dGV4LmMgICAgICAgICAgICAgICAgICAgIHwgOTggKysrKysrKysrKysrKysrKysrKysr KysrKysrKy0tLQoga2VybmVsL2xvY2tpbmcvdGVzdC13d19tdXRleC5jICAgICAgICAgICAgfCAg MiArLQogbGliL2xvY2tpbmctc2VsZnRlc3QuYyAgICAgICAgICAgICAgICAgICAgfCAgMiArLQog OCBmaWxlcyBjaGFuZ2VkLCAxNTIgaW5zZXJ0aW9ucygrKSwgMzIgZGVsZXRpb25zKC0pCgpkaWZm IC0tZ2l0IGEvRG9jdW1lbnRhdGlvbi9sb2NraW5nL3d3LW11dGV4LWRlc2lnbi50eHQgYi9Eb2N1 bWVudGF0aW9uL2xvY2tpbmcvd3ctbXV0ZXgtZGVzaWduLnR4dAppbmRleCAzNGMzYTFiNTBiOWEu LjI5Yzg1NjIzYjU1MSAxMDA2NDQKLS0tIGEvRG9jdW1lbnRhdGlvbi9sb2NraW5nL3d3LW11dGV4 LWRlc2lnbi50eHQKKysrIGIvRG9jdW1lbnRhdGlvbi9sb2NraW5nL3d3LW11dGV4LWRlc2lnbi50 eHQKQEAgLTEsNCArMSw0IEBACi1XYWl0L1dvdW5kIERlYWRsb2NrLVByb29mIE11dGV4IERlc2ln bgorV291bmQvV2FpdCBEZWFkbG9jay1Qcm9vZiBNdXRleCBEZXNpZ24KID09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09CiAKIFBsZWFzZSByZWFkIG11dGV4LWRlc2lnbi50eHQg Zmlyc3QsIGFzIGl0IGFwcGxpZXMgdG8gd2FpdC93b3VuZCBtdXRleGVzIHRvby4KQEAgLTMyLDEw ICszMiwyMyBAQCB0aGUgb2xkZXN0IHRhc2spIHdpbnMsIGFuZCB0aGUgb25lIHdpdGggdGhlIGhp Z2hlciByZXNlcnZhdGlvbiBpZCAoaS5lLiB0aGUKIHlvdW5nZXIgdGFzaykgdW5sb2NrcyBhbGwg b2YgdGhlIGJ1ZmZlcnMgdGhhdCBpdCBoYXMgYWxyZWFkeSBsb2NrZWQsIGFuZCB0aGVuCiB0cmll cyBhZ2Fpbi4KIAotSW4gdGhlIFJEQk1TIGxpdGVyYXR1cmUgdGhpcyBkZWFkbG9jayBoYW5kbGlu ZyBhcHByb2FjaCBpcyBjYWxsZWQgd2FpdC93b3VuZDoKLVRoZSBvbGRlciB0YXNrcyB3YWl0cyB1 bnRpbCBpdCBjYW4gYWNxdWlyZSB0aGUgY29udGVuZGVkIGxvY2suIFRoZSB5b3VuZ2VyIHRhc2tz Ci1uZWVkcyB0byBiYWNrIG9mZiBhbmQgZHJvcCBhbGwgdGhlIGxvY2tzIGl0IGlzIGN1cnJlbnRs eSBob2xkaW5nLCBpLmUuIHRoZQoteW91bmdlciB0YXNrIGlzIHdvdW5kZWQuCitJbiB0aGUgUkRC TVMgbGl0ZXJhdHVyZSwgYSByZXNlcnZhdGlvbiB0aWNrZXQgaXMgYXNzb2NpYXRlZCB3aXRoIGEg dHJhbnNhY3Rpb24uCithbmQgdGhlIGRlYWRsb2NrIGhhbmRsaW5nIGFwcHJvYWNoIGlzIGNhbGxl ZCBXYWl0LURpZS4gVGhlIG5hbWUgaXMgYmFzZWQgb24KK3RoZSBhY3Rpb25zIG9mIGEgbG9ja2lu ZyB0aHJlYWQgd2hlbiBpdCBlbmNvdW50ZXJzIGFuIGFscmVhZHkgbG9ja2VkIG11dGV4LgorSWYg dGhlIHRyYW5zYWN0aW9uIGhvbGRpbmcgdGhlIGxvY2sgaXMgeW91bmdlciwgdGhlIGxvY2tpbmcg dHJhbnNhY3Rpb24gd2FpdHMuCitJZiB0aGUgdHJhbnNhY3Rpb24gaG9sZGluZyB0aGUgbG9jayBp cyBvbGRlciwgdGhlIGxvY2tpbmcgdHJhbnNhY3Rpb24gYmFja3Mgb2ZmCithbmQgZGllcy4gSGVu Y2UgV2FpdC1EaWUuCitUaGVyZSBpcyBhbHNvIGFub3RoZXIgYWxnb3JpdGhtIGNhbGxlZCBXb3Vu ZC1XYWl0OgorSWYgdGhlIHRyYW5zYWN0aW9uIGhvbGRpbmcgdGhlIGxvY2sgaXMgeW91bmdlciwg dGhlIGxvY2tpbmcgdHJhbnNhY3Rpb24KK3ByZWVtcHRzIHRoZSB0cmFuc2FjdGlvbiBob2xkaW5n IHRoZSBsb2NrLCByZXF1aXJpbmcgaXQgdG8gYmFjayBvZmYuIEl0CitXb3VuZHMgdGhlIG90aGVy IHRyYW5zYWN0aW9uLgorSWYgdGhlIHRyYW5zYWN0aW9uIGhvbGRpbmcgdGhlIGxvY2sgaXMgb2xk ZXIsIGl0IHdhaXRzIGZvciB0aGUgb3RoZXIKK3RyYW5zYWN0aW9uLiBIZW5jZSBXb3VuZC1XYWl0 LgorVGhlIHR3byBhbGdvcml0aG1zIGFyZSBib3RoIGZhaXIgaW4gdGhhdCBhIHRyYW5zYWN0aW9u IHdpbGwgZXZlbnR1YWxseSBzdWNjZWVkLgorSG93ZXZlciwgdGhlIFdvdW5kLVdhaXQgYWxnb3Jp dGhtIGlzIHR5cGljYWxseSBzdGF0ZWQgdG8gZ2VuZXJhdGUgZmV3ZXIgYmFja29mZnMKK2NvbXBh cmVkIHRvIFdhaXQtRGllLCBidXQgaXMsIG9uIHRoZSBvdGhlciBoYW5kLCBhc3NvY2lhdGVkIHdp dGggbW9yZSB3b3JrIHRoYW4KK1dhaXQtRGllIHdoZW4gcmVjb3ZlcmluZyBmcm9tIGEgYmFja29m Zi4gV291bmQtV2FpdCBpcyBhbHNvIGEgcHJlZW1wdGl2ZQorYWxnb3JpdGhtIHdoaWNoIHJlcXVp cmVzIGEgcmVsaWFibGUgd2F5IHRvIHByZWVtcHQgYW5vdGhlciB0cmFuc2FjdGlvbi4KIAogQ29u Y2VwdHMKIC0tLS0tLS0tCkBAIC00NywxMCArNjAsMTIgQEAgQWNxdWlyZSBjb250ZXh0OiBUbyBl bnN1cmUgZXZlbnR1YWwgZm9yd2FyZCBwcm9ncmVzcyBpdCBpcyBpbXBvcnRhbnQgdGhlIGEgdGFz awogdHJ5aW5nIHRvIGFjcXVpcmUgbG9ja3MgZG9lc24ndCBncmFiIGEgbmV3IHJlc2VydmF0aW9u IGlkLCBidXQga2VlcHMgdGhlIG9uZSBpdAogYWNxdWlyZWQgd2hlbiBzdGFydGluZyB0aGUgbG9j ayBhY3F1aXNpdGlvbi4gVGhpcyB0aWNrZXQgaXMgc3RvcmVkIGluIHRoZQogYWNxdWlyZSBjb250 ZXh0LiBGdXJ0aGVybW9yZSB0aGUgYWNxdWlyZSBjb250ZXh0IGtlZXBzIHRyYWNrIG9mIGRlYnVn Z2luZyBzdGF0ZQotdG8gY2F0Y2ggdy93IG11dGV4IGludGVyZmFjZSBhYnVzZS4KK3RvIGNhdGNo IHcvdyBtdXRleCBpbnRlcmZhY2UgYWJ1c2UuIEFuIGFjcXVpcmUgY29udGV4dCBpcyByZXByZXNl bnRpbmcgYQordHJhbnNhY3Rpb24uCiAKIFcvdyBjbGFzczogSW4gY29udHJhc3QgdG8gbm9ybWFs IG11dGV4ZXMgdGhlIGxvY2sgY2xhc3MgbmVlZHMgdG8gYmUgZXhwbGljaXQgZm9yCi13L3cgbXV0 ZXhlcywgc2luY2UgaXQgaXMgcmVxdWlyZWQgdG8gaW5pdGlhbGl6ZSB0aGUgYWNxdWlyZSBjb250 ZXh0Lgordy93IG11dGV4ZXMsIHNpbmNlIGl0IGlzIHJlcXVpcmVkIHRvIGluaXRpYWxpemUgdGhl IGFjcXVpcmUgY29udGV4dC4gVGhlIGxvY2sKK2NsYXNzIGFsc28gc3BlY2lmaWVzIHdoYXQgYWxn b3JpdGhtIHRvIHVzZSwgV291bmQtV2FpdCBvciBXYWl0LURpZS4KIAogRnVydGhlcm1vcmUgdGhl cmUgYXJlIHRocmVlIGRpZmZlcmVudCBjbGFzcyBvZiB3L3cgbG9jayBhY3F1aXJlIGZ1bmN0aW9u czoKIApAQCAtOTAsMTAgKzEwNSwxNSBAQCBwcm92aWRlZC4KIFVzYWdlCiAtLS0tLQogCitUaGUg YWxnb3JpdGhtIChXYWl0LURpZSB2cyBXb3VuZC1XYWl0KSBpcyBjaG9zZW4gdXNpbmcgdGhlIF9p c193YWl0X2RpZQorYXJndW1lbnQgdG8gREVGSU5FX1dXX0NMQVNTKCkuIEFzIGEgcm91Z2ggcnVs ZSBvZiB0aHVtYiwgdXNlIFdvdW5kLVdhaXQgaWZmIHlvdQordHlwaWNhbGx5IGV4cGVjdCB0aGUg bnVtYmVyIG9mIHNpbXVsdGFuZW91cyBjb21wZXRpbmcgdHJhbnNhY3Rpb25zIHRvIGJlIHNtYWxs LAorYW5kIHRoZSByb2xsYmFjayBjb3N0IGNhbiBiZSBzdWJzdGFudGlhbC4KKwogVGhyZWUgZGlm ZmVyZW50IHdheXMgdG8gYWNxdWlyZSBsb2NrcyB3aXRoaW4gdGhlIHNhbWUgdy93IGNsYXNzLiBD b21tb24KIGRlZmluaXRpb25zIGZvciBtZXRob2RzICMxIGFuZCAjMjoKIAotc3RhdGljIERFRklO RV9XV19DTEFTUyh3d19jbGFzcyk7CitzdGF0aWMgREVGSU5FX1dXX0NMQVNTKHd3X2NsYXNzLCBm YWxzZSk7CiAKIHN0cnVjdCBvYmogewogCXN0cnVjdCB3d19tdXRleCBsb2NrOwpAQCAtMjQzLDcg KzI2Myw3IEBAIHN0cnVjdCBvYmogewogCXN0cnVjdCBsaXN0X2hlYWQgbG9ja2VkX2xpc3Q7CiB9 OwogCi1zdGF0aWMgREVGSU5FX1dXX0NMQVNTKHd3X2NsYXNzKTsKK3N0YXRpYyBERUZJTkVfV1df Q0xBU1Mod3dfY2xhc3MsIGZhbHNlKTsKIAogdm9pZCBfX3VubG9ja19vYmpzKHN0cnVjdCBsaXN0 X2hlYWQgKmxpc3QpCiB7CkBAIC0zMTIsMTIgKzMzMiwyMyBAQCBEZXNpZ246CiAgIFdlIG1haW50 YWluIHRoZSBmb2xsb3dpbmcgaW52YXJpYW50cyBmb3IgdGhlIHdhaXQgbGlzdDoKICAgKDEpIFdh aXRlcnMgd2l0aCBhbiBhY3F1aXJlIGNvbnRleHQgYXJlIHNvcnRlZCBieSBzdGFtcCBvcmRlcjsg d2FpdGVycwogICAgICAgd2l0aG91dCBhbiBhY3F1aXJlIGNvbnRleHQgYXJlIGludGVyc3BlcnNl ZCBpbiBGSUZPIG9yZGVyLgotICAoMikgQW1vbmcgd2FpdGVycyB3aXRoIGNvbnRleHRzLCBvbmx5 IHRoZSBmaXJzdCBvbmUgY2FuIGhhdmUgb3RoZXIgbG9ja3MKLSAgICAgIGFjcXVpcmVkIGFscmVh ZHkgKGN0eC0+YWNxdWlyZWQgPiAwKS4gTm90ZSB0aGF0IHRoaXMgd2FpdGVyIG1heSBjb21lCi0g ICAgICBhZnRlciBvdGhlciB3YWl0ZXJzIHdpdGhvdXQgY29udGV4dHMgaW4gdGhlIGxpc3QuCisg ICgyKSBGb3IgV2FpdC1EaWUsIGFtb25nIHdhaXRlcnMgd2l0aCBjb250ZXh0cywgb25seSB0aGUg Zmlyc3Qgb25lIGNhbiBoYXZlCisgICAgICBvdGhlciBsb2NrcyBhY3F1aXJlZCBhbHJlYWR5IChj dHgtPmFjcXVpcmVkID4gMCkuIE5vdGUgdGhhdCB0aGlzIHdhaXRlcgorICAgICAgbWF5IGNvbWUg YWZ0ZXIgb3RoZXIgd2FpdGVycyB3aXRob3V0IGNvbnRleHRzIGluIHRoZSBsaXN0LgorCisgIFRo ZSBXb3VuZC1XYWl0IHByZWVtcHRpb24gaXMgaW1wbGVtZW50ZWQgd2l0aCBhIGxhenktcHJlZW1w dGlvbiBzY2hlbWU6CisgIFRoZSB3b3VuZGVkIHN0YXR1cyBvZiB0aGUgdHJhbnNhY3Rpb24gaXMg Y2hlY2tlZCBvbmx5IHdoZW4gdGhlcmUgaXMKKyAgY29udGVudGlvbiBmb3IgYSBuZXcgbG9jayBh bmQgaGVuY2UgYSB0cnVlIGNoYW5jZSBvZiBkZWFkbG9jay4gSW4gdGhhdAorICBzaXR1YXRpb24s IGlmIHRoZSB0cmFuc2FjdGlvbiBpcyB3b3VuZGVkLCBpdCBiYWNrcyBvZmYsIGNsZWFycyB0aGUK KyAgd291bmRlZCBzdGF0dXMgYW5kIHJldHJpZXMuIEEgZ3JlYXQgYmVuZWZpdCBvZiBpbXBsZW1l bnRpbmcgcHJlZW1wdGlvbiBpbgorICB0aGlzIHdheSBpcyB0aGF0IHRoZSB3b3VuZGVkIHRyYW5z YWN0aW9uIGNhbiBpZGVudGlmeSBhIGNvbnRlbmRpbmcgbG9jayB0bworICB3YWl0IGZvciBiZWZv cmUgcmVzdGFydGluZyB0aGUgdHJhbnNhY3Rpb24uIEp1c3QgYmxpbmRseSByZXN0YXJ0aW5nIHRo ZQorICB0cmFuc2FjdGlvbiB3b3VsZCBsaWtlbHkgbWFrZSB0aGUgdHJhbnNhY3Rpb24gZW5kIHVw IGluIGEgc2l0dWF0aW9uIHdoZXJlCisgIGl0IHdvdWxkIGhhdmUgdG8gYmFjayBvZmYgYWdhaW4u CiAKICAgSW4gZ2VuZXJhbCwgbm90IG11Y2ggY29udGVudGlvbiBpcyBleHBlY3RlZC4gVGhlIGxv Y2tzIGFyZSB0eXBpY2FsbHkgdXNlZCB0bwotICBzZXJpYWxpemUgYWNjZXNzIHRvIHJlc291cmNl cyBmb3IgZGV2aWNlcy4KKyAgc2VyaWFsaXplIGFjY2VzcyB0byByZXNvdXJjZXMgZm9yIGRldmlj ZXMsIGFuZCBvcHRpbWl6YXRpb24gZm9jdXMgc2hvdWxkCisgIHRoZXJlZm9yZSBiZSBkaXJlY3Rl ZCB0b3dhcmRzIHRoZSB1bmNvbnRlbmRlZCBjYXNlcy4KIAogTG9ja2RlcDoKICAgU3BlY2lhbCBj YXJlIGhhcyBiZWVuIHRha2VuIHRvIHdhcm4gZm9yIGFzIG1hbnkgY2FzZXMgb2YgYXBpIGFidXNl CmRpZmYgLS1naXQgYS9kcml2ZXJzL2RtYS1idWYvcmVzZXJ2YXRpb24uYyBiL2RyaXZlcnMvZG1h LWJ1Zi9yZXNlcnZhdGlvbi5jCmluZGV4IDMxNGViMTA3MWNjZS4uMDM5NTcxYjlmZWExIDEwMDY0 NAotLS0gYS9kcml2ZXJzL2RtYS1idWYvcmVzZXJ2YXRpb24uYworKysgYi9kcml2ZXJzL2RtYS1i dWYvcmVzZXJ2YXRpb24uYwpAQCAtNDYsNyArNDYsNyBAQAogICogd3JpdGUtc2lkZSB1cGRhdGVz LgogICovCiAKLURFRklORV9XV19DTEFTUyhyZXNlcnZhdGlvbl93d19jbGFzcyk7CitERUZJTkVf V1dfQ0xBU1MocmVzZXJ2YXRpb25fd3dfY2xhc3MsIHRydWUpOwogRVhQT1JUX1NZTUJPTChyZXNl cnZhdGlvbl93d19jbGFzcyk7CiAKIHN0cnVjdCBsb2NrX2NsYXNzX2tleSByZXNlcnZhdGlvbl9z ZXFjb3VudF9jbGFzczsKZGlmZiAtLWdpdCBhL2RyaXZlcnMvZ3B1L2RybS9kcm1fbW9kZXNldF9s b2NrLmMgYi9kcml2ZXJzL2dwdS9kcm0vZHJtX21vZGVzZXRfbG9jay5jCmluZGV4IDhhNTEwMDY4 NTg3NS4uZjIyYTdlZjQxZGUxIDEwMDY0NAotLS0gYS9kcml2ZXJzL2dwdS9kcm0vZHJtX21vZGVz ZXRfbG9jay5jCisrKyBiL2RyaXZlcnMvZ3B1L2RybS9kcm1fbW9kZXNldF9sb2NrLmMKQEAgLTcw LDcgKzcwLDcgQEAKICAqIGxpc3RzIGFuZCBsb29rdXAgZGF0YSBzdHJ1Y3R1cmVzLgogICovCiAK LXN0YXRpYyBERUZJTkVfV1dfQ0xBU1MoY3J0Y193d19jbGFzcyk7CitzdGF0aWMgREVGSU5FX1dX X0NMQVNTKGNydGNfd3dfY2xhc3MsIHRydWUpOwogCiAvKioKICAqIGRybV9tb2Rlc2V0X2xvY2tf YWxsIC0gdGFrZSBhbGwgbW9kZXNldCBsb2NrcwpkaWZmIC0tZ2l0IGEvaW5jbHVkZS9saW51eC93 d19tdXRleC5oIGIvaW5jbHVkZS9saW51eC93d19tdXRleC5oCmluZGV4IDM5ZmRhMTk1YmY3OC4u NjI3ODA3N2YyODhiIDEwMDY0NAotLS0gYS9pbmNsdWRlL2xpbnV4L3d3X211dGV4LmgKKysrIGIv aW5jbHVkZS9saW51eC93d19tdXRleC5oCkBAIC04LDYgKzgsOCBAQAogICoKICAqIFdvdW5kL3dh aXQgaW1wbGVtZW50YXRpb246CiAgKiAgQ29weXJpZ2h0IChDKSAyMDEzIENhbm9uaWNhbCBMdGQu CisgKiBDaG9pY2Ugb2YgYWxnb3JpdGhtOgorICogIENvcHlyaWdodCAoQykgMjAxOCBXTVdhcmUg SW5jLgogICoKICAqIFRoaXMgZmlsZSBjb250YWlucyB0aGUgbWFpbiBkYXRhIHN0cnVjdHVyZSBh bmQgQVBJIGRlZmluaXRpb25zLgogICovCkBAIC0yMywxNSArMjUsMTcgQEAgc3RydWN0IHd3X2Ns YXNzIHsKIAlzdHJ1Y3QgbG9ja19jbGFzc19rZXkgbXV0ZXhfa2V5OwogCWNvbnN0IGNoYXIgKmFj cXVpcmVfbmFtZTsKIAljb25zdCBjaGFyICptdXRleF9uYW1lOworCWJvb2wgaXNfd2FpdF9kaWU7 CiB9OwogCiBzdHJ1Y3Qgd3dfYWNxdWlyZV9jdHggewogCXN0cnVjdCB0YXNrX3N0cnVjdCAqdGFz azsKIAl1bnNpZ25lZCBsb25nIHN0YW1wOwogCXVuc2lnbmVkIGFjcXVpcmVkOworCWJvb2wgd291 bmRlZDsKKwlzdHJ1Y3Qgd3dfY2xhc3MgKnd3X2NsYXNzOwogI2lmZGVmIENPTkZJR19ERUJVR19N VVRFWEVTCiAJdW5zaWduZWQgZG9uZV9hY3F1aXJlOwotCXN0cnVjdCB3d19jbGFzcyAqd3dfY2xh c3M7CiAJc3RydWN0IHd3X211dGV4ICpjb250ZW5kaW5nX2xvY2s7CiAjZW5kaWYKICNpZmRlZiBD T05GSUdfREVCVUdfTE9DS19BTExPQwpAQCAtNTgsMTcgKzYyLDE5IEBAIHN0cnVjdCB3d19tdXRl eCB7CiAjIGRlZmluZSBfX1dXX0NMQVNTX01VVEVYX0lOSVRJQUxJWkVSKGxvY2tuYW1lLCBjbGFz cykKICNlbmRpZgogCi0jZGVmaW5lIF9fV1dfQ0xBU1NfSU5JVElBTElaRVIod3dfY2xhc3MpIFwK KyNkZWZpbmUgX19XV19DTEFTU19JTklUSUFMSVpFUih3d19jbGFzcywgX2lzX3dhaXRfZGllKQkg ICAgXAogCQl7IC5zdGFtcCA9IEFUT01JQ19MT05HX0lOSVQoMCkgXAogCQksIC5hY3F1aXJlX25h bWUgPSAjd3dfY2xhc3MgIl9hY3F1aXJlIiBcCi0JCSwgLm11dGV4X25hbWUgPSAjd3dfY2xhc3Mg Il9tdXRleCIgfQorCQksIC5tdXRleF9uYW1lID0gI3d3X2NsYXNzICJfbXV0ZXgiIFwKKwkJLCAu aXNfd2FpdF9kaWUgPSBfaXNfd2FpdF9kaWUgfQogCiAjZGVmaW5lIF9fV1dfTVVURVhfSU5JVElB TElaRVIobG9ja25hbWUsIGNsYXNzKSBcCiAJCXsgLmJhc2UgPSAgX19NVVRFWF9JTklUSUFMSVpF Uihsb2NrbmFtZS5iYXNlKSBcCiAJCV9fV1dfQ0xBU1NfTVVURVhfSU5JVElBTElaRVIobG9ja25h bWUsIGNsYXNzKSB9CiAKLSNkZWZpbmUgREVGSU5FX1dXX0NMQVNTKGNsYXNzbmFtZSkgXAotCXN0 cnVjdCB3d19jbGFzcyBjbGFzc25hbWUgPSBfX1dXX0NMQVNTX0lOSVRJQUxJWkVSKGNsYXNzbmFt ZSkKKyNkZWZpbmUgREVGSU5FX1dXX0NMQVNTKGNsYXNzbmFtZSwgX2lzX3dhaXRfZGllKQkJCVwK KwlzdHJ1Y3Qgd3dfY2xhc3MgY2xhc3NuYW1lID0gX19XV19DTEFTU19JTklUSUFMSVpFUihjbGFz c25hbWUsIFwKKwkJCQkJCQkgICBfaXNfd2FpdF9kaWUpCiAKICNkZWZpbmUgREVGSU5FX1dXX01V VEVYKG11dGV4bmFtZSwgd3dfY2xhc3MpIFwKIAlzdHJ1Y3Qgd3dfbXV0ZXggbXV0ZXhuYW1lID0g X19XV19NVVRFWF9JTklUSUFMSVpFUihtdXRleG5hbWUsIHd3X2NsYXNzKQpAQCAtMTIzLDggKzEy OSw5IEBAIHN0YXRpYyBpbmxpbmUgdm9pZCB3d19hY3F1aXJlX2luaXQoc3RydWN0IHd3X2FjcXVp cmVfY3R4ICpjdHgsCiAJY3R4LT50YXNrID0gY3VycmVudDsKIAljdHgtPnN0YW1wID0gYXRvbWlj X2xvbmdfaW5jX3JldHVybl9yZWxheGVkKCZ3d19jbGFzcy0+c3RhbXApOwogCWN0eC0+YWNxdWly ZWQgPSAwOwotI2lmZGVmIENPTkZJR19ERUJVR19NVVRFWEVTCiAJY3R4LT53d19jbGFzcyA9IHd3 X2NsYXNzOworCWN0eC0+d291bmRlZCA9IGZhbHNlOworI2lmZGVmIENPTkZJR19ERUJVR19NVVRF WEVTCiAJY3R4LT5kb25lX2FjcXVpcmUgPSAwOwogCWN0eC0+Y29udGVuZGluZ19sb2NrID0gTlVM TDsKICNlbmRpZgpkaWZmIC0tZ2l0IGEva2VybmVsL2xvY2tpbmcvbG9ja3RvcnR1cmUuYyBiL2tl cm5lbC9sb2NraW5nL2xvY2t0b3J0dXJlLmMKaW5kZXggNjg1MGZmZDY5MTI1Li43NzhlZDAyNjM4 MmYgMTAwNjQ0Ci0tLSBhL2tlcm5lbC9sb2NraW5nL2xvY2t0b3J0dXJlLmMKKysrIGIva2VybmVs L2xvY2tpbmcvbG9ja3RvcnR1cmUuYwpAQCAtMzY1LDcgKzM2NSw3IEBAIHN0YXRpYyBzdHJ1Y3Qg bG9ja190b3J0dXJlX29wcyBtdXRleF9sb2NrX29wcyA9IHsKIH07CiAKICNpbmNsdWRlIDxsaW51 eC93d19tdXRleC5oPgotc3RhdGljIERFRklORV9XV19DTEFTUyh0b3J0dXJlX3d3X2NsYXNzKTsK K3N0YXRpYyBERUZJTkVfV1dfQ0xBU1ModG9ydHVyZV93d19jbGFzcywgdHJ1ZSk7CiBzdGF0aWMg REVGSU5FX1dXX01VVEVYKHRvcnR1cmVfd3dfbXV0ZXhfMCwgJnRvcnR1cmVfd3dfY2xhc3MpOwog c3RhdGljIERFRklORV9XV19NVVRFWCh0b3J0dXJlX3d3X211dGV4XzEsICZ0b3J0dXJlX3d3X2Ns YXNzKTsKIHN0YXRpYyBERUZJTkVfV1dfTVVURVgodG9ydHVyZV93d19tdXRleF8yLCAmdG9ydHVy ZV93d19jbGFzcyk7CmRpZmYgLS1naXQgYS9rZXJuZWwvbG9ja2luZy9tdXRleC5jIGIva2VybmVs L2xvY2tpbmcvbXV0ZXguYwppbmRleCAyMDQ4MzU5ZjMzZDIuLmI0NDlhMDEyYzZmOSAxMDA2NDQK LS0tIGEva2VybmVsL2xvY2tpbmcvbXV0ZXguYworKysgYi9rZXJuZWwvbG9ja2luZy9tdXRleC5j CkBAIC0yOTAsMTIgKzI5MCw0NyBAQCBfX3d3X2N0eF9zdGFtcF9hZnRlcihzdHJ1Y3Qgd3dfYWNx dWlyZV9jdHggKmEsIHN0cnVjdCB3d19hY3F1aXJlX2N0eCAqYikKIAkgICAgICAgKGEtPnN0YW1w ICE9IGItPnN0YW1wIHx8IGEgPiBiKTsKIH0KIAorLyoKKyAqIFdvdW5kIHRoZSBsb2NrIGhvbGRl ciB0cmFuc2FjdGlvbiBpZiBpdCdzIHlvdW5nZXIgdGhhbiB0aGUgY29udGVuZGluZworICogdHJh bnNhY3Rpb24sIGFuZCB0aGVyZSBpcyBhIHBvc3NpYmlsaXR5IG9mIGEgZGVhZGxvY2suCisgKiBB bHNvIGlmIHRoZSBsb2NrIGhvbGRlciB0cmFuc2FjdGlvbiBpc24ndCB0aGUgY3VycmVudCB0cmFu c2FjdGlvbiwKKyAqIE1ha2Ugc3VyZSBpdCdzIHdva2VuIHVwIGluIGNhc2UgaXQncyBzbGVlcGlu ZyBvbiBhbm90aGVyIHd3IG11dGV4LgorICovCitzdGF0aWMgYm9vbCBfX3d3X211dGV4X3dvdW5k KHN0cnVjdCBtdXRleCAqbG9jaywKKwkJCSAgICAgc3RydWN0IHd3X2FjcXVpcmVfY3R4ICp3d19j dHgsCisJCQkgICAgIHN0cnVjdCB3d19hY3F1aXJlX2N0eCAqaG9sZF9jdHgpCit7CisJc3RydWN0 IHRhc2tfc3RydWN0ICpvd25lciA9CisJCV9fb3duZXJfdGFzayhhdG9taWNfbG9uZ19yZWFkKCZs b2NrLT5vd25lcikpOworCisJbG9ja2RlcF9hc3NlcnRfaGVsZCgmbG9jay0+d2FpdF9sb2NrKTsK KworCWlmIChvd25lciAmJiBob2xkX2N0eCAmJiBfX3d3X2N0eF9zdGFtcF9hZnRlcihob2xkX2N0 eCwgd3dfY3R4KSAmJgorCSAgICB3d19jdHgtPmFjcXVpcmVkID4gMCkgeworCQlXUklURV9PTkNF KGhvbGRfY3R4LT53b3VuZGVkLCB0cnVlKTsKKwkJaWYgKG93bmVyICE9IGN1cnJlbnQpIHsKKwkJ CS8qCisJCQkgKiB3YWtlX3VwX3Byb2Nlc3MoKSBpbnNlcnRzIGEgd3JpdGUgbWVtb3J5IGJhcnJp ZXIgdG8KKwkJCSAqIG1ha2Ugc3VyZSBvd25lciBzZWVzIGl0IGlzIHdvdW5kZWQgYmVmb3JlCisJ CQkgKiBUQVNLX1JVTk5JTkcgaW4gY2FzZSBpdCdzIHNsZWVwaW5nIG9uIGFub3RoZXIKKwkJCSAq IHd3X211dGV4LiBOb3RlIHRoYXQgb3duZXIgcG9pbnRzIHRvIGEgdmFsaWQKKwkJCSAqIHRhc2tf c3RydWN0IGFzIGxvbmcgYXMgd2UgaG9sZCB0aGUgd2FpdF9sb2NrLgorCQkJICovCisJCQl3YWtl X3VwX3Byb2Nlc3Mob3duZXIpOworCQl9CisJCXJldHVybiB0cnVlOworCX0KKworCXJldHVybiBm YWxzZTsKK30KKwogLyoKICAqIFdha2UgdXAgYW55IHdhaXRlcnMgdGhhdCBtYXkgaGF2ZSB0byBi YWNrIG9mZiB3aGVuIHRoZSBsb2NrIGlzIGhlbGQgYnkgdGhlCiAgKiBnaXZlbiBjb250ZXh0Lgog ICoKICAqIER1ZSB0byB0aGUgaW52YXJpYW50cyBvbiB0aGUgd2FpdCBsaXN0LCB0aGlzIGNhbiBv bmx5IGFmZmVjdCB0aGUgZmlyc3QKLSAqIHdhaXRlciB3aXRoIGEgY29udGV4dC4KKyAqIHdhaXRl ciB3aXRoIGEgY29udGV4dCwgdW5sZXNzIHRoZSBXb3VuZC1XYWl0IGFsZ29yaXRobSBpcyB1c2Vk IHdoZXJlCisgKiBhbHNvIHN1YnNlcXVlbnQgd2FpdGVycyB3aXRoIGEgY29udGV4dCBtYWluIHdv dW5kIHRoZSBsb2NrIGhvbGRlci4KICAqCiAgKiBUaGUgY3VycmVudCB0YXNrIG11c3Qgbm90IGJl IG9uIHRoZSB3YWl0IGxpc3QuCiAgKi8KQEAgLTMwMyw2ICszMzgsNyBAQCBzdGF0aWMgdm9pZCBf X3NjaGVkCiBfX3d3X211dGV4X3dha2V1cF9mb3JfYmFja29mZihzdHJ1Y3QgbXV0ZXggKmxvY2ss IHN0cnVjdCB3d19hY3F1aXJlX2N0eCAqd3dfY3R4KQogewogCXN0cnVjdCBtdXRleF93YWl0ZXIg KmN1cjsKKwlib29sIGlzX3dhaXRfZGllID0gd3dfY3R4LT53d19jbGFzcy0+aXNfd2FpdF9kaWU7 CiAKIAlsb2NrZGVwX2Fzc2VydF9oZWxkKCZsb2NrLT53YWl0X2xvY2spOwogCkBAIC0zMTAsMTMg KzM0NiwxNCBAQCBfX3d3X211dGV4X3dha2V1cF9mb3JfYmFja29mZihzdHJ1Y3QgbXV0ZXggKmxv Y2ssIHN0cnVjdCB3d19hY3F1aXJlX2N0eCAqd3dfY3R4KQogCQlpZiAoIWN1ci0+d3dfY3R4KQog CQkJY29udGludWU7CiAKLQkJaWYgKGN1ci0+d3dfY3R4LT5hY3F1aXJlZCA+IDAgJiYKKwkJaWYg KGlzX3dhaXRfZGllICYmIGN1ci0+d3dfY3R4LT5hY3F1aXJlZCA+IDAgJiYKIAkJICAgIF9fd3df Y3R4X3N0YW1wX2FmdGVyKGN1ci0+d3dfY3R4LCB3d19jdHgpKSB7CiAJCQlkZWJ1Z19tdXRleF93 YWtlX3dhaXRlcihsb2NrLCBjdXIpOwogCQkJd2FrZV91cF9wcm9jZXNzKGN1ci0+dGFzayk7CiAJ CX0KIAotCQlicmVhazsKKwkJaWYgKGlzX3dhaXRfZGllIHx8IF9fd3dfbXV0ZXhfd291bmQobG9j aywgY3VyLT53d19jdHgsIHd3X2N0eCkpCisJCQlicmVhazsKIAl9CiB9CiAKQEAgLTMzOCwxMiAr Mzc1LDE3IEBAIHd3X211dGV4X3NldF9jb250ZXh0X2Zhc3RwYXRoKHN0cnVjdCB3d19tdXRleCAq bG9jaywgc3RydWN0IHd3X2FjcXVpcmVfY3R4ICpjdHgpCiAJICogYW5kIGtlZXAgc3Bpbm5pbmcs IG9yIGl0IHdpbGwgYWNxdWlyZSB3YWl0X2xvY2ssIGFkZCBpdHNlbGYKIAkgKiB0byB3YWl0ZXIg bGlzdCBhbmQgc2xlZXAuCiAJICovCi0Jc21wX21iKCk7IC8qIF5eXiAqLworCXNtcF9tYigpOyAv KiBTZWUgY29tbWVudHMgYWJvdmUgYW5kIGJlbG93LiAqLwogCiAJLyoKLQkgKiBDaGVjayBpZiBs b2NrIGlzIGNvbnRlbmRlZCwgaWYgbm90IHRoZXJlIGlzIG5vYm9keSB0byB3YWtlIHVwCisJICog Q2hlY2sgaWYgbG9jayBpcyBjb250ZW5kZWQsIGlmIG5vdCB0aGVyZSBpcyBub2JvZHkgdG8gd2Fr ZSB1cC4KKwkgKiBDaGVja2luZyBNVVRFWF9GTEFHX1dBSVRFUlMgaXMgbm90IGVub3VnaCBoZXJl LCBzaW5jZSB3ZSBuZWVkIHRvCisJICogb3JkZXIgYWdhaW5zdCB0aGUgbG9jay0+Y3R4IGNoZWNr IGluIF9fd3dfbXV0ZXhfd291bmQgY2FsbGVkIGZyb20KKwkgKiBfX3d3X211dGV4X2FkZF93YWl0 ZXIuIFdlIGNhbiB1c2UgbGlzdF9lbXB0eSB3aXRob3V0IHRha2luZyB0aGUKKwkgKiB3YWl0X2xv Y2ssIGdpdmVuIHRoZSBtZW1vcnkgYmFycmllciBhYm92ZSBhbmQgdGhlIGxpc3RfZW1wdHkKKwkg KiBkb2N1bWVudGF0aW9uLgogCSAqLwotCWlmIChsaWtlbHkoIShhdG9taWNfbG9uZ19yZWFkKCZs b2NrLT5iYXNlLm93bmVyKSAmIE1VVEVYX0ZMQUdfV0FJVEVSUykpKQorCWlmIChsaWtlbHkobGlz dF9lbXB0eSgmbG9jay0+YmFzZS53YWl0X2xpc3QpKSkKIAkJcmV0dXJuOwogCiAJLyoKQEAgLTY1 Myw2ICs2OTUsMTcgQEAgX193d19tdXRleF9sb2NrX2NoZWNrX3N0YW1wKHN0cnVjdCBtdXRleCAq bG9jaywgc3RydWN0IG11dGV4X3dhaXRlciAqd2FpdGVyLAogCXN0cnVjdCB3d19hY3F1aXJlX2N0 eCAqaG9sZF9jdHggPSBSRUFEX09OQ0Uod3ctPmN0eCk7CiAJc3RydWN0IG11dGV4X3dhaXRlciAq Y3VyOwogCisJLyoKKwkgKiBJZiB3ZSBtaXNzIGEgd291bmRlZCA9PSB0cnVlIGhlcmUsIHdlIHdp bGwgaGF2ZSBhIHBlbmRpbmcKKwkgKiBUQVNLX1JVTk5JTkcgYW5kIHBpY2sgaXQgdXAgb24gdGhl IG5leHQgc2NoZWR1bGUgZmFsbC10aHJvdWdoLgorCSAqLworCWlmICghY3R4LT53d19jbGFzcy0+ aXNfd2FpdF9kaWUpIHsKKwkJaWYgKFJFQURfT05DRShjdHgtPndvdW5kZWQpKQorCQkJZ290byBk ZWFkbG9jazsKKwkJZWxzZQorCQkJcmV0dXJuIDA7CisJfQorCiAJaWYgKGhvbGRfY3R4ICYmIF9f d3dfY3R4X3N0YW1wX2FmdGVyKGN0eCwgaG9sZF9jdHgpKQogCQlnb3RvIGRlYWRsb2NrOwogCkBA IC02ODMsMTIgKzczNiwxNSBAQCBfX3d3X211dGV4X2FkZF93YWl0ZXIoc3RydWN0IG11dGV4X3dh aXRlciAqd2FpdGVyLAogewogCXN0cnVjdCBtdXRleF93YWl0ZXIgKmN1cjsKIAlzdHJ1Y3QgbGlz dF9oZWFkICpwb3M7CisJYm9vbCBpc193YWl0X2RpZTsKIAogCWlmICghd3dfY3R4KSB7CiAJCWxp c3RfYWRkX3RhaWwoJndhaXRlci0+bGlzdCwgJmxvY2stPndhaXRfbGlzdCk7CiAJCXJldHVybiAw OwogCX0KIAorCWlzX3dhaXRfZGllID0gd3dfY3R4LT53d19jbGFzcy0+aXNfd2FpdF9kaWU7CisK IAkvKgogCSAqIEFkZCB0aGUgd2FpdGVyIGJlZm9yZSB0aGUgZmlyc3Qgd2FpdGVyIHdpdGggYSBo aWdoZXIgc3RhbXAuCiAJICogV2FpdGVycyB3aXRob3V0IGEgY29udGV4dCBhcmUgc2tpcHBlZCB0 byBhdm9pZCBzdGFydmluZwpAQCAtNzAxLDcgKzc1Nyw3IEBAIF9fd3dfbXV0ZXhfYWRkX3dhaXRl cihzdHJ1Y3QgbXV0ZXhfd2FpdGVyICp3YWl0ZXIsCiAKIAkJaWYgKF9fd3dfY3R4X3N0YW1wX2Fm dGVyKHd3X2N0eCwgY3VyLT53d19jdHgpKSB7CiAJCQkvKiBCYWNrIG9mZiBpbW1lZGlhdGVseSBp ZiBuZWNlc3NhcnkuICovCi0JCQlpZiAod3dfY3R4LT5hY3F1aXJlZCA+IDApIHsKKwkJCWlmIChp c193YWl0X2RpZSAmJiB3d19jdHgtPmFjcXVpcmVkID4gMCkgewogI2lmZGVmIENPTkZJR19ERUJV R19NVVRFWEVTCiAJCQkJc3RydWN0IHd3X211dGV4ICp3dzsKIApAQCAtNzIxLDEzICs3NzcsMjYg QEAgX193d19tdXRleF9hZGRfd2FpdGVyKHN0cnVjdCBtdXRleF93YWl0ZXIgKndhaXRlciwKIAkJ ICogV2FrZSB1cCB0aGUgd2FpdGVyIHNvIHRoYXQgaXQgZ2V0cyBhIGNoYW5jZSB0byBiYWNrCiAJ CSAqIG9mZi4KIAkJICovCi0JCWlmIChjdXItPnd3X2N0eC0+YWNxdWlyZWQgPiAwKSB7CisJCWlm IChpc193YWl0X2RpZSAmJiBjdXItPnd3X2N0eC0+YWNxdWlyZWQgPiAwKSB7CiAJCQlkZWJ1Z19t dXRleF93YWtlX3dhaXRlcihsb2NrLCBjdXIpOwogCQkJd2FrZV91cF9wcm9jZXNzKGN1ci0+dGFz ayk7CiAJCX0KIAl9CiAKIAlsaXN0X2FkZF90YWlsKCZ3YWl0ZXItPmxpc3QsIHBvcyk7CisJaWYg KCFpc193YWl0X2RpZSkgeworCQlzdHJ1Y3Qgd3dfbXV0ZXggKnd3ID0gY29udGFpbmVyX29mKGxv Y2ssIHN0cnVjdCB3d19tdXRleCwgYmFzZSk7CisKKwkJLyoKKwkJICogTWFrZSBzdXJlIGEgcmFj aW5nIGxvY2sgdGFrZXIgc2VlcyBhIG5vbi1lbXB0eSB3YWl0aW5nIGxpc3QKKwkJICogYmVmb3Jl IHdlIHJlYWQgd3ctPmN0eCwgc28gdGhhdCBpZiB3ZSBtaXNzIHd3LT5jdHgsIHRoZQorCQkgKiBy YWNpbmcgbG9jayB0YWtlciB3aWxsIGNhbGwgX193d19tdXRleF93YWtlX3VwX2Zvcl9iYWNrb2Zm KCkKKwkJICogYW5kIHdvdW5kIGl0c2VsZi4KKwkJICovCisJCXNtcF9tYigpOworCQlfX3d3X211 dGV4X3dvdW5kKGxvY2ssIHd3X2N0eCwgd3ctPmN0eCk7CisJfQorCiAJcmV0dXJuIDA7CiB9CiAK QEAgLTc1MCw2ICs4MTksMTQgQEAgX19tdXRleF9sb2NrX2NvbW1vbihzdHJ1Y3QgbXV0ZXggKmxv Y2ssIGxvbmcgc3RhdGUsIHVuc2lnbmVkIGludCBzdWJjbGFzcywKIAlpZiAodXNlX3d3X2N0eCAm JiB3d19jdHgpIHsKIAkJaWYgKHVubGlrZWx5KHd3X2N0eCA9PSBSRUFEX09OQ0Uod3ctPmN0eCkp KQogCQkJcmV0dXJuIC1FQUxSRUFEWTsKKworCQkvKgorCQkgKiBSZXNldCB0aGUgd291bmRlZCBm bGFnIGFmdGVyIGEgYmFja29mZi4KKwkJICogTm8gb3RoZXIgcHJvY2VzcyBjYW4gcmFjZSBhbmQg d291bmQgdXMgaGVyZSBzaW5jZSB0aGV5CisJCSAqIGNhbid0IGhhdmUgYSB2YWxpZCBvd25lciBw b2ludGVyIGF0IHRoaXMgdGltZQorCQkgKi8KKwkJaWYgKHd3X2N0eC0+YWNxdWlyZWQgPT0gMCkK KwkJCXd3X2N0eC0+d291bmRlZCA9IGZhbHNlOwogCX0KIAogCXByZWVtcHRfZGlzYWJsZSgpOwpA QCAtODU4LDYgKzkzNSwxMSBAQCBfX211dGV4X2xvY2tfY29tbW9uKHN0cnVjdCBtdXRleCAqbG9j aywgbG9uZyBzdGF0ZSwgdW5zaWduZWQgaW50IHN1YmNsYXNzLAogYWNxdWlyZWQ6CiAJX19zZXRf Y3VycmVudF9zdGF0ZShUQVNLX1JVTk5JTkcpOwogCisJLyogV2Ugc3RvbGUgdGhlIGxvY2suIE5l ZWQgdG8gY2hlY2sgd291bmRlZCBzdGF0dXMuICovCisJaWYgKHVzZV93d19jdHggJiYgd3dfY3R4 ICYmICF3d19jdHgtPnd3X2NsYXNzLT5pc193YWl0X2RpZSAmJgorCSAgICAhX19tdXRleF93YWl0 ZXJfaXNfZmlyc3QobG9jaywgJndhaXRlcikpCisJCV9fd3dfbXV0ZXhfd2FrZXVwX2Zvcl9iYWNr b2ZmKGxvY2ssIHd3X2N0eCk7CisKIAltdXRleF9yZW1vdmVfd2FpdGVyKGxvY2ssICZ3YWl0ZXIs IGN1cnJlbnQpOwogCWlmIChsaWtlbHkobGlzdF9lbXB0eSgmbG9jay0+d2FpdF9saXN0KSkpCiAJ CV9fbXV0ZXhfY2xlYXJfZmxhZyhsb2NrLCBNVVRFWF9GTEFHUyk7CmRpZmYgLS1naXQgYS9rZXJu ZWwvbG9ja2luZy90ZXN0LXd3X211dGV4LmMgYi9rZXJuZWwvbG9ja2luZy90ZXN0LXd3X211dGV4 LmMKaW5kZXggMGU0Y2Q2NGFkMmMwLi5jN2ZjMTEyZDY5MWQgMTAwNjQ0Ci0tLSBhL2tlcm5lbC9s b2NraW5nL3Rlc3Qtd3dfbXV0ZXguYworKysgYi9rZXJuZWwvbG9ja2luZy90ZXN0LXd3X211dGV4 LmMKQEAgLTI2LDcgKzI2LDcgQEAKICNpbmNsdWRlIDxsaW51eC9zbGFiLmg+CiAjaW5jbHVkZSA8 bGludXgvd3dfbXV0ZXguaD4KIAotc3RhdGljIERFRklORV9XV19DTEFTUyh3d19jbGFzcyk7Citz dGF0aWMgREVGSU5FX1dXX0NMQVNTKHd3X2NsYXNzLCB0cnVlKTsKIHN0cnVjdCB3b3JrcXVldWVf c3RydWN0ICp3cTsKIAogc3RydWN0IHRlc3RfbXV0ZXggewpkaWZmIC0tZ2l0IGEvbGliL2xvY2tp bmctc2VsZnRlc3QuYyBiL2xpYi9sb2NraW5nLXNlbGZ0ZXN0LmMKaW5kZXggYjVjMTI5M2NlMTQ3 Li5lNTIwNjVmMmFjYmYgMTAwNjQ0Ci0tLSBhL2xpYi9sb2NraW5nLXNlbGZ0ZXN0LmMKKysrIGIv bGliL2xvY2tpbmctc2VsZnRlc3QuYwpAQCAtMjksNyArMjksNyBAQAogICovCiBzdGF0aWMgdW5z aWduZWQgaW50IGRlYnVnX2xvY2tzX3ZlcmJvc2U7CiAKLXN0YXRpYyBERUZJTkVfV1dfQ0xBU1Mo d3dfbG9ja2RlcCk7CitzdGF0aWMgREVGSU5FX1dXX0NMQVNTKHd3X2xvY2tkZXAsIHRydWUpOwog CiBzdGF0aWMgaW50IF9faW5pdCBzZXR1cF9kZWJ1Z19sb2Nrc192ZXJib3NlKGNoYXIgKnN0cikK IHsKLS0gCjIuMTQuMwoKX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX18KZHJpLWRldmVsIG1haWxpbmcgbGlzdApkcmktZGV2ZWxAbGlzdHMuZnJlZWRlc2t0b3Au b3JnCmh0dHBzOi8vbGlzdHMuZnJlZWRlc2t0b3Aub3JnL21haWxtYW4vbGlzdGluZm8vZHJpLWRl dmVsCg== From mboxrd@z Thu Jan 1 00:00:00 1970 Return-path: Received: from mail-eopbgr720071.outbound.protection.outlook.com ([40.107.72.71]:65056 "EHLO NAM05-CO1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S934508AbeFMHsl (ORCPT ); Wed, 13 Jun 2018 03:48:41 -0400 From: Thomas Hellstrom To: dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org Cc: Thomas Hellstrom , Peter Zijlstra , 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 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes Date: Wed, 13 Jun 2018 09:47:44 +0200 Message-Id: <20180613074745.14750-2-thellstrom@vmware.com> In-Reply-To: <20180613074745.14750-1-thellstrom@vmware.com> References: <20180613074745.14750-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-04 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: Peter Zijlstra 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 Signed-off-by: Thomas Hellstrom --- 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 | 19 ++++-- kernel/locking/locktorture.c | 2 +- kernel/locking/mutex.c | 98 ++++++++++++++++++++++++++++--- kernel/locking/test-ww_mutex.c | 2 +- lib/locking-selftest.c | 2 +- 8 files changed, 152 insertions(+), 32 deletions(-) diff --git a/Documentation/locking/ww-mutex-design.txt b/Documentation/locking/ww-mutex-design.txt index 34c3a1b50b9a..29c85623b551 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,23 @@ 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/wound: -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 is wounded. +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 +preempts the transaction holding the lock, requiring it to back off. It +Wounds the other transaction. +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 which requires a reliable way to preempt another transaction. Concepts -------- @@ -47,10 +60,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,10 +105,15 @@ provided. Usage ----- +The algorithm (Wait-Die vs Wound-Wait) is chosen using the _is_wait_die +argument to DEFINE_WW_CLASS(). As a rough rule of thumb, use Wound-Wait iff you +typically expect the number of simultaneous competing transactions to be small, +and the rollback cost can be substantial. + Three different ways to acquire locks within the same w/w class. Common definitions for methods #1 and #2: -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WW_CLASS(ww_class, false); struct obj { struct ww_mutex lock; @@ -243,7 +263,7 @@ struct obj { struct list_head locked_list; }; -static DEFINE_WW_CLASS(ww_class); +static DEFINE_WW_CLASS(ww_class, false); void __unlock_objs(struct list_head *list) { @@ -312,12 +332,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..039571b9fea1 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_WW_CLASS(reservation_ww_class, true); 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..f22a7ef41de1 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_WW_CLASS(crtc_ww_class, true); /** * drm_modeset_lock_all - take all modeset locks diff --git a/include/linux/ww_mutex.h b/include/linux/ww_mutex.h index 39fda195bf78..6278077f288b 100644 --- a/include/linux/ww_mutex.h +++ b/include/linux/ww_mutex.h @@ -8,6 +8,8 @@ * * Wound/wait 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,15 +25,17 @@ struct ww_class { struct lock_class_key mutex_key; const char *acquire_name; const char *mutex_name; + bool is_wait_die; }; struct ww_acquire_ctx { struct task_struct *task; unsigned long stamp; unsigned acquired; + bool wounded; + struct ww_class *ww_class; #ifdef CONFIG_DEBUG_MUTEXES unsigned done_acquire; - struct ww_class *ww_class; struct ww_mutex *contending_lock; #endif #ifdef CONFIG_DEBUG_LOCK_ALLOC @@ -58,17 +62,19 @@ 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_WW_CLASS(classname) \ - struct ww_class classname = __WW_CLASS_INITIALIZER(classname) +#define DEFINE_WW_CLASS(classname, _is_wait_die) \ + struct ww_class classname = __WW_CLASS_INITIALIZER(classname, \ + _is_wait_die) #define DEFINE_WW_MUTEX(mutexname, ww_class) \ struct ww_mutex mutexname = __WW_MUTEX_INITIALIZER(mutexname, ww_class) @@ -123,8 +129,9 @@ 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; -#ifdef CONFIG_DEBUG_MUTEXES ctx->ww_class = ww_class; + ctx->wounded = false; +#ifdef CONFIG_DEBUG_MUTEXES ctx->done_acquire = 0; ctx->contending_lock = NULL; #endif diff --git a/kernel/locking/locktorture.c b/kernel/locking/locktorture.c index 6850ffd69125..778ed026382f 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_WW_CLASS(torture_ww_class, true); 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 2048359f33d2..b449a012c6f9 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -290,12 +290,47 @@ __ww_ctx_stamp_after(struct ww_acquire_ctx *a, struct ww_acquire_ctx *b) (a->stamp != b->stamp || a > b); } +/* + * Wound the lock holder transaction if it's younger than the contending + * transaction, and there is a possibility of a deadlock. + * Also if the lock holder transaction isn't the current transaction, + * Make sure it's woken up in case it's sleeping on another ww mutex. + */ +static bool __ww_mutex_wound(struct mutex *lock, + struct ww_acquire_ctx *ww_ctx, + struct ww_acquire_ctx *hold_ctx) +{ + struct task_struct *owner = + __owner_task(atomic_long_read(&lock->owner)); + + lockdep_assert_held(&lock->wait_lock); + + if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) && + ww_ctx->acquired > 0) { + WRITE_ONCE(hold_ctx->wounded, true); + if (owner != current) { + /* + * wake_up_process() inserts a write memory barrier to + * make sure owner sees it is wounded before + * TASK_RUNNING in case it's sleeping on another + * ww_mutex. Note that owner points to a valid + * task_struct as long as we hold the wait_lock. + */ + wake_up_process(owner); + } + return true; + } + + return false; +} + /* * Wake up any waiters that may have to back off when the lock is held by the * given context. * * Due to the invariants on the wait list, this can only affect the first - * waiter with a context. + * waiter with a context, unless the Wound-Wait algorithm is used where + * also subsequent waiters with a context main wound the lock holder. * * The current task must not be on the wait list. */ @@ -303,6 +338,7 @@ static void __sched __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) { struct mutex_waiter *cur; + bool is_wait_die = ww_ctx->ww_class->is_wait_die; lockdep_assert_held(&lock->wait_lock); @@ -310,13 +346,14 @@ __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) if (!cur->ww_ctx) continue; - if (cur->ww_ctx->acquired > 0 && + if (is_wait_die && cur->ww_ctx->acquired > 0 && __ww_ctx_stamp_after(cur->ww_ctx, ww_ctx)) { debug_mutex_wake_waiter(lock, cur); wake_up_process(cur->task); } - break; + if (is_wait_die || __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx)) + break; } } @@ -338,12 +375,17 @@ 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 + * Check if lock is contended, if not there is nobody to wake up. + * Checking MUTEX_FLAG_WAITERS is not enough here, since we need to + * order against the lock->ctx check in __ww_mutex_wound called from + * __ww_mutex_add_waiter. We can use list_empty without taking the + * wait_lock, given the memory barrier above and the list_empty + * documentation. */ - if (likely(!(atomic_long_read(&lock->base.owner) & MUTEX_FLAG_WAITERS))) + if (likely(list_empty(&lock->base.wait_list))) return; /* @@ -653,6 +695,17 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct mutex_waiter *waiter, struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx); struct mutex_waiter *cur; + /* + * If we miss a wounded == true here, we will have a pending + * TASK_RUNNING and pick it up on the next schedule fall-through. + */ + if (!ctx->ww_class->is_wait_die) { + if (READ_ONCE(ctx->wounded)) + goto deadlock; + else + return 0; + } + if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx)) goto deadlock; @@ -683,12 +736,15 @@ __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); return 0; } + is_wait_die = ww_ctx->ww_class->is_wait_die; + /* * Add the waiter before the first waiter with a higher stamp. * Waiters without a context are skipped to avoid starving @@ -701,7 +757,7 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, if (__ww_ctx_stamp_after(ww_ctx, cur->ww_ctx)) { /* Back off immediately if necessary. */ - if (ww_ctx->acquired > 0) { + if (is_wait_die && ww_ctx->acquired > 0) { #ifdef CONFIG_DEBUG_MUTEXES struct ww_mutex *ww; @@ -721,13 +777,26 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, * Wake up the waiter so that it gets a chance to back * off. */ - if (cur->ww_ctx->acquired > 0) { + if (is_wait_die && cur->ww_ctx->acquired > 0) { debug_mutex_wake_waiter(lock, cur); wake_up_process(cur->task); } } list_add_tail(&waiter->list, pos); + if (!is_wait_die) { + struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); + + /* + * Make sure a racing lock taker sees a non-empty waiting list + * before we read ww->ctx, so that if we miss ww->ctx, the + * racing lock taker will call __ww_mutex_wake_up_for_backoff() + * and wound itself. + */ + smp_mb(); + __ww_mutex_wound(lock, ww_ctx, ww->ctx); + } + return 0; } @@ -750,6 +819,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 backoff. + * No other process can race and wound us here since they + * can't have a valid owner pointer at this time + */ + if (ww_ctx->acquired == 0) + ww_ctx->wounded = false; } preempt_disable(); @@ -858,6 +935,11 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, acquired: __set_current_state(TASK_RUNNING); + /* We stole the lock. Need to check wounded status. */ + if (use_ww_ctx && ww_ctx && !ww_ctx->ww_class->is_wait_die && + !__mutex_waiter_is_first(lock, &waiter)) + __ww_mutex_wakeup_for_backoff(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..c7fc112d691d 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_WW_CLASS(ww_class, true); struct workqueue_struct *wq; struct test_mutex { diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c index b5c1293ce147..e52065f2acbf 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_WW_CLASS(ww_lockdep, true); static int __init setup_debug_locks_verbose(char *str) { -- 2.14.3