From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752753AbcHKPBj (ORCPT ); Thu, 11 Aug 2016 11:01:39 -0400 Received: from mail-cys01nam02on0122.outbound.protection.outlook.com ([104.47.37.122]:54625 "EHLO NAM02-CY1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751839AbcHKPBh (ORCPT ); Thu, 11 Aug 2016 11:01:37 -0400 X-Greylist: delayed 162082 seconds by postgrey-1.27 at vger.kernel.org; Thu, 11 Aug 2016 11:01:37 EDT Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=waiman.long@hpe.com; Message-ID: <57AC9347.1060105@hpe.com> Date: Thu, 11 Aug 2016 11:01:27 -0400 From: Waiman Long User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.12) Gecko/20130109 Thunderbird/10.0.12 MIME-Version: 1.0 To: Waiman Long CC: Ingo Molnar , Peter Zijlstra , , Linus Torvalds , Ding Tianhong , Jason Low , Davidlohr Bueso , "Paul E. McKenney" , Thomas Gleixner , Will Deacon , Tim Chen , Imre Deak Subject: Re: [PATCH v5 3/3] locking/mutex: Ensure forward progress of waiter-spinner References: <1470853530-37540-1-git-send-email-Waiman.Long@hpe.com> <1470853530-37540-4-git-send-email-Waiman.Long@hpe.com> In-Reply-To: <1470853530-37540-4-git-send-email-Waiman.Long@hpe.com> Content-Type: text/plain; charset="ISO-8859-1"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [72.71.243.167] X-ClientProxiedBy: BN6PR17CA0012.namprd17.prod.outlook.com (10.173.147.22) To DF4PR84MB0316.NAMPRD84.PROD.OUTLOOK.COM (10.162.193.30) X-MS-Office365-Filtering-Correlation-Id: d8c4a82f-533e-4cfc-c706-08d3c1f862a6 X-Microsoft-Exchange-Diagnostics: 1;DF4PR84MB0316;2:md3eVN1ggIkD3/FmJSnrZPLmcUtIZ+ry1q1SziGk5XYnmTsszs+I1mll82ZNzsGgmCPFYH3p/dO4AXcz0u3dco3Dga+cpMynp3QWs/9hPzP251vvQuIL8AGUNEIPK/h4bVv1xHrfI+ILTK2bFPLB4aP8LpHdtSF53esMg9RPDdhsiQA6S4sKyyGuRWDP0VVk;3:iMARNPPAIbWfHbbmcdqlLS5zruYSG5s3XwNacY2aZ8SVzw5fJeMAj2GFTHSr5xVc7RyhE0uMXxqGyfb97hI2nN5Em+pNihbGDrNgRjh8jhgRuc43HeeeLGeCfnoXZF5h;25:wJz5VkEPO7s9+yxyKbs2iGcm0lXeZiOxthkIaMpDtaSqm65IP8dvYuvAAOWpuiFzM86HF9NGmfeUJRQvhbxeFC/fWkHiK5wxynvUtXVYOPbpWjH9M++kLCcPL3JVlyA9QbRu5ZGmSyqUjluqTJ5yCFOMGTqAe896W69o87fMR2GfYW5qcQ8JbEeCDFVftEqw8FuYETGYyw3y2Uow+5d1Qbvu1ZewcWeD2OkMH08u751OCxU5uVsowZvkPg7lv0HWnh9vt7O7k9bdbkiqYucH4uWzLNTe0AFkWZ0aDMlTFglf0oMGgxH5gdFGgHooYCcviboizY+ZDk0vYUOCSSECK8KH3z79LklFErDKPqjJr0SBjFb7cue+ZMrkXkclh9GCwYmjLRp4VF9WS1ueysPcmUHOuW5WMpnAIdPlxsR+97I= X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:DF4PR84MB0316; X-Microsoft-Exchange-Diagnostics: 1;DF4PR84MB0316;31:NPIxH0eyMGQtuJrMmZ4b5PPQ+g4aEiYzUp2DeTgL/HksLSaaM7DNh9PwlKdMLDwGMDFZQbnoB5XWaNMsGT3puv/JVzajumYx+rV6OF5w33z6g7IBN0dTbT/lUyX1mtdTyOMu9Z1iOIBRj+BUHIkCt2IsC4M13tAGvT4SX5seyb1JSJgn88lJoMISJLvQ66uxPfi+dCD81mSxAIQdJN9Pj2hlQSmN5y4aLVIlrXavAG0=;20:K53iSb4ek2GRKAddn/QuE50C/REsaIte+Fu2NdisQY8CwDTXYafGB+LyEsyDngeGHkG547LptQ5ndZwWGGlrsVrr1JVvdQxHDPv0ny8+IL2lkfOVzVH6p/6gjODWGPnyQLtgEy5S1czdn1EyJbhfd64uQFndHt0suGz9ZCJalYVsd2n/Guwp4BndzoA8IBGzYO4ku3ai0bvBDXTYIFN+L+b4VwwZIFI4xc5JG1FcTX6BGIFm68WldBGo+aw+nSbDEqUIJ+JSMySBOzKYmpAj3edooTL5cJvVHLaI1T5ASFsFXuksfbnxE9PZpSrxhchkZPSzusM7OjTyjuJuCNdkFHDGPrvM1UX4f0B3iPzt/biN1Oum4fBslUUNQHrhjM4LZSKpwufuGUPsFhncknAMNT2j3KDq0SdIIGOtXx9DhErnlG/1oBOlgkuOjYhXuEY6ObqcEPCxM0eQJcy2+B5Lw4hej2iaqYY0KiKWiFcbR4Frz0T19dT6/0UNrFanASYg X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(190756311086443)(227479698468861); X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001)(6055026);SRVR:DF4PR84MB0316;BCL:0;PCL:0;RULEID:;SRVR:DF4PR84MB0316; X-Microsoft-Exchange-Diagnostics: 1;DF4PR84MB0316;4:4aI2vv1mTnIS3U2Il3fov+cMzAx/vOBPo/FM4gI36xlR//B7GLlTKnTLODx8KtpqqxehhwIT+lVcw3t0xUQqRbZQPDqqN2vSUI2s/RoHj2Hs0Ck0RIMB8MMIupcEkeudBUCRMHgE/QGn2yLOLI8QHaZIdkn/8jUp5NAHmObI1Qmg8D2gHHonStfMjtI1s32WuAqlwnXzXxF5L4Kcb2vuK/OuwvhAL0OBfssnV6VvisVM6SkXiTl+PTzZoPTJmVLp+OCyeBDxFkfcKVeBL9kVKjxoYUDUzyGw6hoKHlvkCdVA4gHfgfaCw8aF9y9x6zY9Dv8zjqhQCdkXMV7vAadMsqT9E5gN/Il79BJi8KCF4VWUAOOC0GZ98tDPVkp8Q4CsztSdr5HzqVvt66qiwI2/2DeLOGOa2nvmWhRWMlD6apHJe42rcvRZ6vG3OvmryaDy3R3jv/pFAvwGinmphllUrw== X-Forefront-PRVS: 0031A0FFAF X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6009001)(6049001)(7916002)(24454002)(189002)(199003)(377454003)(2906002)(105586002)(8676002)(81156014)(50986999)(106356001)(4326007)(65816999)(81166006)(33656002)(6116002)(76176999)(87266999)(101416001)(3846002)(54356999)(77096005)(2950100001)(230700001)(64126003)(23756003)(586003)(50466002)(59896002)(189998001)(110136002)(92566002)(65806001)(66066001)(4001350100001)(65956001)(117156001)(97736004)(19580405001)(19580395003)(80316001)(7846002)(86362001)(8666005)(47776003)(7736002)(305945005)(42186005)(7416002)(68736007)(36756003)(83506001)(6200100001)(7059030);DIR:OUT;SFP:1102;SCL:1;SRVR:DF4PR84MB0316;H:[192.168.142.185];FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?iso-8859-1?Q?1;DF4PR84MB0316;23:Xu0y/DwgrXEVaToQMQWEY2xwkiyCs5iOMPNt7RP?= =?iso-8859-1?Q?p1rbzSQqY0yNT7tl0JY1VLLXzJYPcPhvHIi9v3dszEblxqslpmIpF4ibL1?= =?iso-8859-1?Q?j8pN73UoXojsZ3qOGj7vdU2x8WyBDdy9cdFQRxfTlnhe+FbXtTMiXJ6GzP?= =?iso-8859-1?Q?eJXsLBWlwGplq3445MzZgWc0P9Um0QnVTocLQcBf6r6W5sPEAOpzKmHg28?= =?iso-8859-1?Q?xa4sol1fWK2sMeEBTWOgUiD5hLS4TUYKCCR/KHzDWz72qm29+CrSzM0Kis?= =?iso-8859-1?Q?7LcOd3dM9uV0PZaueHzn8ffYARVT8B7himy5Tuhq+6SSo1GWwsyuPtQ6rt?= =?iso-8859-1?Q?SS0ultekdw8kUmidetAX5bze/5mS+zZFO1WaVs4Rq8JBLCOgVCQPIQ6wD9?= =?iso-8859-1?Q?3KhEeETVWCo9rvG4gN5v2z5L8YP5PE2aGA9GoaifykRjSYXI18DAxP//dH?= =?iso-8859-1?Q?b8W14Ckbod6PsWx5LetoUaxER1FZMxd3cPg0j86eIhKCrZUumn6qS0YbIx?= =?iso-8859-1?Q?WYHapQGMaTq+t2qIrqr7GRVmve6qwUFpCxsQmBr7KCqFg9EgzT99BZEjO3?= =?iso-8859-1?Q?lIKNeP8XXeGtmIuT+uWt+KUnFBJsG2J9SmJV3O5KtGKVcqUsAnom2Jh8SI?= =?iso-8859-1?Q?FAthGKmb+44A75rbdB9UyCtD9LAIMqYOtTu6q46vne6NQb78nd3d7+0Udx?= =?iso-8859-1?Q?vFmao2j6u6i/8V8dNKNQUE8KrpGuwOwUOlJPj4btIuqk826CVHFuvuTKtK?= =?iso-8859-1?Q?lifuLXKLE7hJS7ONt4N19rTf3nKomKcGlqeytHxPsyOxA1IhljOKRfX/Fj?= =?iso-8859-1?Q?YP/csQgW/mBbrz1lgb4jieunKNdeNOPHUX22ux9CjuT7zyTiIsrglxkKhf?= =?iso-8859-1?Q?kkfXxvCWXXctgqHrM0e/3h9bJhrJSnDoxUqMcD6l+Sd1xfAXRUc2vVwhoY?= =?iso-8859-1?Q?X7Wm6E8wEmmKc/aSEw5WoNiMHQgUyKANX9Aw6D1IcwJD9NZ9kwPn/BH5jk?= =?iso-8859-1?Q?i+ZQBspUqUrJMp+P5hQB550P041bbS2KlVKZF7tZcDOobBgZVUQxJb2CDk?= =?iso-8859-1?Q?CoWGY2kajLLnkVQCIfuR+T+sYxYBdItStjr0nSknjinWpVMBqoK76tOm4M?= =?iso-8859-1?Q?Swh7kg9TMRQOzMGfcYeZf5e9REHRi1Afo2saD5bw7iJxc/kPQsFy5Gf8an?= =?iso-8859-1?Q?hHnpyamA7rLx9dOGy/ODruzCFXOegaXQMAYTk73iEOMKuTkUYQL64FCOSr?= =?iso-8859-1?Q?65eeeeoaNyHI8m/fhT8t4KOxy8pIS6rJKEGnWAqqzN3S2PwOEl+ejqJOcS?= =?iso-8859-1?Q?SEvPCMY1pfPuwZBsSHnZUnfhUaAUYthNwrnitJupDheC1iQr0p50lknQoc?= =?iso-8859-1?Q?ld+jovh7V/+I2FdwXxLpnHUYYZZLv7mhYtmsk36PDUFEiP1kfrTEp9XSMA?= =?iso-8859-1?Q?XRZBR30grmlE1Yk0K5ANKD7dItf5winYBbr?= X-Microsoft-Exchange-Diagnostics: 1;DF4PR84MB0316;6:pbjJ9ZuHqE/r0hc9puomP22UoNMooO4wwK6oQkpozKhFQiqD3OtRe1nokiQbhnUNpQTlY6s4WaKnU57ho/40PdYo3tXNe0EWagCLrdsFJTaP69hNeeSN/KbnjC91HVwRqewQxas49/sGdjohWC8EyVFBdHzVv4XLTuAPIWnd1tJ5ZToAylh3mrok97kT67N85ZW4YqxpcdiirY0GLxOatL0gbv1ZoX0TcYDsURIKxFaI6TM4+A+gW+LISvJkKo32YO3/BFtrxDwIHByHbxaNG5P9ovEDeUjVneRIEX4/ehJXDxzgKQetckrcXDAmnRUQAIB8soz1qVjcNOT9rZfQsA==;5:ZBKxxb0Stu4tnV2kn22+dN5NI+MK6snnd4XtgudwtgZ3rVIBc58cN4qp5rhRshEjCvpAX1Zkgw3//c5Ty8BUiZuZvr8R4RWCUT9SHDJx0lZJDegAC3NH9jhzSH4bgz7ZoNV4O9Yrn4Siu0dXPOPKVw==;24:z53OvDczWjXR/0igghzo06pbZLhi76LmWgPpFPuUo4AM3i+xXDH3pAgLfvvFmjcmtMylcLCCxMAkMCHf6/QR3mue7HdWXeBtouwFmjLEi9E=;7:DV1DbRyTBG1VThQCdqtoXfthwRq0dXHmvXu6/ItQgZ7SWQ/EEuXwtWGrzj059hveIP4j9aXEmgmWqL4ngJhastAdhp9aprdFZIk0kbNoX10d4jJ63RNFQQTUj9qDH83pVVa9EQAutDtlp2aOOUeQ9lBIoO10j2ZT1wDY7mhxsMzVhBtKGRAde1PUZ8/AU57TDMrtWH2j108Px2Ipd90zwyzY/VW6ePzmrP+M0QWlVHdkWQuhBoZuwuVKV8tjP4/W SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: hpe.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 11 Aug 2016 15:01:32.9779 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: DF4PR84MB0316 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/10/2016 02:25 PM, Waiman Long wrote: > As both an optimistic spinner and a waiter-spinner (a woken task from > the wait queue spinning) can be spinning on the lock at the same time, > we cannot ensure forward progress for the waiter-spinner. So it is > possible for the waiter-spinner to be starved of getting the lock, > though not likely. > > This patch adds a flag to indicate that a waiter-spinner is > spinning and hence has priority over the acquisition of the lock. A > waiter-spinner sets this flag while spinning. An optimistic spinner > will check this flag and yield if set. This essentially makes the > waiter-spinner jump to the head of the optimistic spinning queue to > acquire the lock. > > There will be no increase in size for the mutex structure for > 64-bit architectures as there is an existing 4-byte hole. For 32-bit > architectures, there will be a size increase of 4 bytes. > > Signed-off-by: Waiman Long > --- > include/linux/mutex.h | 1 + > kernel/locking/mutex.c | 36 +++++++++++++++++++++++++++--------- > 2 files changed, 28 insertions(+), 9 deletions(-) > > diff --git a/include/linux/mutex.h b/include/linux/mutex.h > index 2cb7531..f8e91ad 100644 > --- a/include/linux/mutex.h > +++ b/include/linux/mutex.h > @@ -57,6 +57,7 @@ struct mutex { > #endif > #ifdef CONFIG_MUTEX_SPIN_ON_OWNER > struct optimistic_spin_queue osq; /* Spinner MCS lock */ > + int waiter_spinning; > #endif > #ifdef CONFIG_DEBUG_MUTEXES > void *magic; > diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c > index 15b521a..0912964 100644 > --- a/kernel/locking/mutex.c > +++ b/kernel/locking/mutex.c > @@ -55,6 +55,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key) > mutex_clear_owner(lock); > #ifdef CONFIG_MUTEX_SPIN_ON_OWNER > osq_lock_init(&lock->osq); > + lock->waiter_spinning = false; > #endif > > debug_mutex_init(lock, name, key); > @@ -337,9 +338,21 @@ static bool mutex_optimistic_spin(struct mutex *lock, > */ > if (!osq_lock(&lock->osq)) > goto done; > + } else { > + /* > + * Turn on the waiter spinning flag to discourage the spinner > + * from getting the lock. > + */ > + lock->waiter_spinning = true; > } > > - while (true) { > + /* > + * The cpu_relax_lowlatency() call is a compiler barrier which forces > + * everything in this loop to be re-loaded. We don't need memory > + * barriers as we'll eventually observe the right values at the cost > + * of a few extra spins. > + */ > + for (;; cpu_relax_lowlatency()) { > struct task_struct *owner; > > if (use_ww_ctx&& ww_ctx->acquired> 0) { > @@ -359,6 +372,17 @@ static bool mutex_optimistic_spin(struct mutex *lock, > } > > /* > + * For regular opt-spinner, it waits until the waiter_spinning > + * flag isn't set. This will ensure forward progress for > + * the waiter spinner. > + */ > + if (!waiter&& READ_ONCE(lock->waiter_spinning)) { > + if (need_resched()) > + break; > + continue; > + } > + > + /* > * If there's an owner, wait for it to either > * release the lock or go to sleep. > */ > @@ -390,18 +414,12 @@ static bool mutex_optimistic_spin(struct mutex *lock, > */ > if (!owner&& (need_resched() || rt_task(task))) > break; > - > - /* > - * The cpu_relax() call is a compiler barrier which forces > - * everything in this loop to be re-loaded. We don't need > - * memory barriers as we'll eventually observe the right > - * values at the cost of a few extra spins. > - */ > - cpu_relax_lowlatency(); > } > > if (!waiter) > osq_unlock(&lock->osq); > + else > + lock->waiter_spinning = false; > done: > /* > * If we fell out of the spin path because of need_resched(), The following is the updated patch that should fix the build error in non-x86 platform. Cheers, Longman ================================ cut here ================================ locking/mutex: Ensure forward progress of waiter-spinner As both an optimistic spinner and a waiter-spinner (a woken task from the wait queue spinning) can be spinning on the lock at the same time, we cannot ensure forward progress for the waiter-spinner. So it is possible for the waiter-spinner to be starved of getting the lock, though not likely. This patch adds a flag to indicate that a waiter-spinner is spinning and hence has priority over the acquisition of the lock. A waiter-spinner sets this flag while spinning. An optimistic spinner will check this flag and yield if set. This essentially makes the waiter-spinner jump to the head of the optimistic spinning queue to acquire the lock. There will be no increase in size for the mutex structure for 64-bit architectures as there is an existing 4-byte hole. For 32-bit architectures, there will be a size increase of 4 bytes. Signed-off-by: Waiman Long --- include/linux/mutex.h | 1 + kernel/locking/mutex.c | 21 +++++++++++++++++++++ 2 files changed, 22 insertions(+), 0 deletions(-) diff --git a/include/linux/mutex.h b/include/linux/mutex.h index 2cb7531..f8e91ad 100644 --- a/include/linux/mutex.h +++ b/include/linux/mutex.h @@ -57,6 +57,7 @@ struct mutex { #endif #ifdef CONFIG_MUTEX_SPIN_ON_OWNER struct optimistic_spin_queue osq; /* Spinner MCS lock */ + int waiter_spinning; #endif #ifdef CONFIG_DEBUG_MUTEXES void *magic; diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index 15b521a..02d8029 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -55,6 +55,7 @@ __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key) mutex_clear_owner(lock); #ifdef CONFIG_MUTEX_SPIN_ON_OWNER osq_lock_init(&lock->osq); + lock->waiter_spinning = false; #endif debug_mutex_init(lock, name, key); @@ -337,6 +338,12 @@ static bool mutex_optimistic_spin(struct mutex *lock, */ if (!osq_lock(&lock->osq)) goto done; + } else { + /* + * Turn on the waiter spinning flag to discourage the spinner + * from getting the lock. + */ + lock->waiter_spinning = true; } while (true) { @@ -359,6 +366,17 @@ static bool mutex_optimistic_spin(struct mutex *lock, } /* + * For regular opt-spinner, it waits until the waiter_spinning + * flag isn't set. This will ensure forward progress for + * the waiter spinner. + */ + if (!waiter && READ_ONCE(lock->waiter_spinning)) { + if (need_resched()) + break; + goto relax; + } + + /* * If there's an owner, wait for it to either * release the lock or go to sleep. */ @@ -391,6 +409,7 @@ static bool mutex_optimistic_spin(struct mutex *lock, if (!owner && (need_resched() || rt_task(task))) break; +relax: /* * The cpu_relax() call is a compiler barrier which forces * everything in this loop to be re-loaded. We don't need @@ -402,6 +421,8 @@ static bool mutex_optimistic_spin(struct mutex *lock, if (!waiter) osq_unlock(&lock->osq); + else + lock->waiter_spinning = false; done: /* * If we fell out of the spin path because of need_resched(), -- 1.7.1