From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932417AbcHIRhY (ORCPT ); Tue, 9 Aug 2016 13:37:24 -0400 Received: from mail-bn3nam01on0125.outbound.protection.outlook.com ([104.47.33.125]:13317 "EHLO NAM01-BN3-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752357AbcHIRhJ (ORCPT ); Tue, 9 Aug 2016 13:37:09 -0400 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=waiman.long@hpe.com; Message-ID: <57AA1493.6090200@hpe.com> Date: Tue, 9 Aug 2016 13:36:19 -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: Peter Zijlstra CC: Ingo Molnar , , Linus Torvalds , Ding Tianhong , Jason Low , Davidlohr Bueso , "Paul E. McKenney" , Thomas Gleixner , Will Deacon , Tim Chen , Imre Deak , Waiman Long Subject: Re: [PATCH v4 1/3] locking/mutex: Add waiter parameter to mutex_optimistic_spin() References: <1468874366-56955-1-git-send-email-Waiman.Long@hpe.com> <1468874366-56955-2-git-send-email-Waiman.Long@hpe.com> <20160808172659.GX6862@twins.programming.kicks-ass.net> In-Reply-To: <20160808172659.GX6862@twins.programming.kicks-ass.net> Content-Type: text/plain; charset="ISO-8859-1"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [72.71.243.211] X-ClientProxiedBy: YQXPR01CA0042.CANPRD01.PROD.OUTLOOK.COM (10.165.102.180) To CS1PR84MB0311.NAMPRD84.PROD.OUTLOOK.COM (10.162.190.29) X-MS-Office365-Filtering-Correlation-Id: 2c768e2e-5733-4c82-4b38-08d3c07bb33a X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0311;2:j7Hh4LoCpoQBbtj6vF7vDuo9wTnrLicvCxhAeV3MFoj6TdnnmcOyCbWBtsruSNijCMxQslh6h+/AwQ8uKfCzpzYUBdOTBFnyoi2UXDgRy1l6ZXQ25KDPC+tFzi3xGn8jatbGEN02SMaoozH5MHtnVbHFUXQMlzXN88q8f+6rkaJcm0AjX9QrtNQZp+FAI1Sw;3:P2vO4sHOgNjxGjJPHrBaOr4M90Go/X13bgATTYgaI95Nwj78nYar2xyzCOuMeI8xmPTQiTA7/8ddRsNS1h/TxvYCC6/N59tGQcQ2zXCJ+pRpKIDn+qyA1CWgBfeaftXw;25:SZ8DN/yXxYvb++qj05jXNlhGsr0aiEp8+tQaPE/MK3hVcWyfNOg7YI9bPd8IPnisPqn1mtuBsuYBxd+4f79RyQ1YFqdc0YqLp7dWLJWF5EvaKTuqv4naOGK83OnVi1g/bNS0y+MGPQ1R68734kWDr1H09YACoLclpRqt26s6+V947l/tKCm+VuANiFLFGPT3UoiNzex00oBQ/vBQtaB8+CCLTR674SZ9IDLcSKq7IVU9q1MzIrG9E3hYNyfLrw8P/x7DWNGyegdBAcJ8a0FK6aPIV82IgvfIxZfOBc6H9o4UCyoHZbgThXFIviz4MExCLkPvql4NcudYw7+VcQK87J0SkgYbr4AQmTzxoCBV7owSxOND0wfHGE+egteZ8Gr2p9uEAojqkPjA06V6aK+mMtLzmTWYRSZRtAYKstlqlY4= X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:CS1PR84MB0311; X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0311;31:huw/FBucv3LFz2BmwUCavs+HaeNZbN2vzqMqJcCZHmuPmI3ndt1aNBr1xKU+vk4o4vLjRC4nCSYKbC0XZ1rsCJxkPSIhjkDOqqPqTNT1nmZPhAjDTLPC01GIa2/o8Mdrzv/BQuwAPoBh2pypJiZ2tCdtXpwAkFFKMCkRKsOVouog74cTCnv+CvfjXK94DZEu3dWKxaOeJELTvba+B/hxpHH+mrvOWyV7ACRz+ctGtfk=;20:sGBR9+xo/pwfApbEYXka7JuCPxPk3HHo1GEJ3Ze5+HuK9CXvog3+lLb7CVV+ZQUbX0L/A9DTsZNyM+uoZmcgNzr+CkbjWUzXgI2G2phqI9bIQeN7eE0kZBDTLMIFLT754ZY5S8Zgb+70VnpqPCgWmz/P7XWx8BoZaH7zccHL0ZA9HUYzGBZ1AcPBeEPTe4RP5O5gdDTkqKOXR+Mj5ZGXNiU+d7NSrZrfH7SHNUdThUu4637/VcVj1iyC3MK0UOXbkgtdi1+X1EioreWkaYqtfWNsxn3fbk3VBKXeQqoizaq2poyFbYcYzH6y2ESWzSsRz5faI5ge1b3xkPK2ceI6qF+NiisKo+LNNqlFEhol4FqU8I7ErrRRLQ+zU/c+fGIiESe2zAy5QYyIxxuW/Sw/6W0wSD4rPHc1bUlDc8tOmrRJk6Z9mhpRBANMpZTuR7huQcDk0KrqcE2o0COplMLhoDVq4Un/bqIzvDNLglZ4pn6sG2Gf632zxjULghTne/pT X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046)(6055026);SRVR:CS1PR84MB0311;BCL:0;PCL:0;RULEID:;SRVR:CS1PR84MB0311; X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0311;4:19qt8puGofGgRw9AUKHYU4/TGG0dXgnAIsAVXFeaEzHWphlcLq+aVUPkgrkYdWRNDAC5ubL8DdVATy6hrQGY3deuGGgEXQOV9Bc3tt4WguwtVNHmkEUDnglAZoKTIl2N17VwrV/Kr8PwDId1q/R5xI0dLicGNad3EKOLEdni+YHMIuxDVS0KMUiKfJQPuJ6CDwY+3Cy1IIyme3fYpDGvr9zkowx0HJCLnozHOTvkCKVG4tQsTbA+wTfGdb01e6B3PUNyR9B9OUzlho9ZgHrvHQgULkHgBG+4WqYrvyU+THw8ywQbU9+fnrNSRyKVb+tXMNbrdaayKezpF1jT90JzpRvNB1sgVQK4Sxqza+1lX/xxO+ukOVBBk7hRQSQk+KROusTSvAPD2Ly0JUQPNQBEEg== X-Forefront-PRVS: 0029F17A3F X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6049001)(6009001)(7916002)(189002)(199003)(377454003)(24454002)(66066001)(68736007)(65956001)(92566002)(4326007)(65806001)(47776003)(59896002)(305945005)(106356001)(7736002)(86362001)(77096005)(586003)(6116002)(3846002)(8666005)(7846002)(2950100001)(2906002)(101416001)(42186005)(65816999)(76176999)(54356999)(87266999)(50986999)(33656002)(230700001)(81166006)(110136002)(97736004)(189998001)(7416002)(81156014)(80316001)(64126003)(105586002)(36756003)(50466002)(83506001)(117156001)(4001350100001)(23756003)(8676002)(7059030);DIR:OUT;SFP:1102;SCL:1;SRVR:CS1PR84MB0311;H:[192.168.142.183];FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?iso-8859-1?Q?1;CS1PR84MB0311;23:8EnP0GXihUxlmyLImr7Sb1mC5oeCine/RGnkXyw?= =?iso-8859-1?Q?2G7a/yrzar0z90hBDK8wLGs9zPSzmY4/d84Pw3Kd7ogkqTLuonnexeKfO+?= =?iso-8859-1?Q?Dsvnqv6OQyLTj7UlBW4J2co8CoKugItcv/TXKVocynCP1v1w+uG0pt5QwS?= =?iso-8859-1?Q?k8Aq2RhbEm+fOvfSJP4+PBoOM4VfPpQl1UxF7iCFNvTMgPoVcUBmlBgHB7?= =?iso-8859-1?Q?K7QgfR+sK+Uw+CoriSLqIEMha/cy/NV0ATYLqaPeELm1pQ7b9dBgalhr7h?= =?iso-8859-1?Q?AB3QWmzKfE34anFYbX7yf6CTLp7i7ORQjy7eSwkj8+GtwUIJ4RuLKoEoHk?= =?iso-8859-1?Q?YZtuTTQU+Jgt39Hl/f4z8TBsUPnF6MfnrbaQFiUEbK0htLhQmOcqLFQ+HR?= =?iso-8859-1?Q?sJLDmMKfe9d9kKdKKhUuZSs8PDtU226X7W8MNIwl4/a4JpA391gPnXewQf?= =?iso-8859-1?Q?+VmTDVeNIzp08CLjvJv/AELaE1Uv+jnR0Tb3iwk2CMfZKTl1mqpYkcYDrV?= =?iso-8859-1?Q?jg7WNn1zmhC+6yG47xvMbmB/InaLh7sx4KThYG9GfO0wNfpoy+Q1mDbJ9r?= =?iso-8859-1?Q?LkrAu5eLGf3L+LvHKepPMFD9lX9QpKpaBSb/MfmRXlN4UibQxjEEczKm4n?= =?iso-8859-1?Q?3TtGisEifow92ONeCerG5dUu0QQNaXOBm1fe9r+O/4kjVM2q+tEEJVTN2S?= =?iso-8859-1?Q?7k1Uj5liOw/LYi/+olMWrdzpB/1cW2cfUkZpzJBdcrR67l2RUdYnGifRMB?= =?iso-8859-1?Q?junHHGYuTy818PyXteB8RZJdR88bkYLzdd11i/JMUUq/THXltMJ+ZSiKxP?= =?iso-8859-1?Q?ZlJ2+PJ5wA2Vd4+VBhjgpZDEnhOeRvfsfSTHR4pNbAL/Z7Fx40di33q2AV?= =?iso-8859-1?Q?GUSWzS/cKnByEBzXKgTB1qJnNnIZsTnd5QC8s3Ob/tjaAyn4SbaF9xZiSc?= =?iso-8859-1?Q?nWsh0diCm2SDrfB9dHjunpjWPMSochRh0N/4I/5eoxZlzHG4vPEdtL56EZ?= =?iso-8859-1?Q?FvmfVSf/a5sB2jiPeBbzfdmGFMaR4lQXo/ap6VMUceSUcrG1jneBZw4y2u?= =?iso-8859-1?Q?0EU+wmIEmR4fssGVuuF/VFJdrDXUC3l4Rs+Q92J7bNKgT26DT0XrdatpsV?= =?iso-8859-1?Q?XyRgwkc/aExRP9DuL//PcVkYxqysfLxoiV9c4BYw+Jd4uhGGSYcsMUwoom?= =?iso-8859-1?Q?/RRpjpedM4q1/NRGD1QvmXFuK+LXTCOsFdG09iS9OSHXB6zolIsUU1FkV0?= =?iso-8859-1?Q?xEYZMc1D1vAXn2CRkfCb5BMpangB7g27oSkAQnJmqVF4OUW1eVzva9AGOU?= =?iso-8859-1?Q?2pA8waT9r6tba+BXmqgyCSaa70Llyu9e0xX7XBeGawUogo35kgqnuLMvEQ?= =?iso-8859-1?Q?Fp2EOCSI=3D?= X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0311;6:uj2ooqNbYTcgPCSM38f+YcaqSVkgRzp24UKs5PVIwxDGXqeI1UY303qC10HeuStm0fa6jJmtoEcei3p5PxoHD3SC8Zp7EOl89JxF0gFc4wpKVleOpMEp5ML6Ncn7v2QjFDkaY+Bz2SsJWgHZfi5T47DFuaJtm7lysmsAN5Q1cHgVXF4if9kYSZ4w+DNgvQOawMWBLq7bCUrqBSbLZbkVm/xgGye3rBx4vC07nQswnPV56RbMNtREZcNGQeVhnrcDS5Usq6Q95YqKnC2BhiJaZkzbdz4u/w6mgOd6V3ZY1uCeZNBkE1rkatFnC5khLctJ2WnuiVy464C5RGofjXrBxw==;5:wD1QlLTe80QICcx+0kRa7oyZiZJ4qk0lPQIVF8edz4CORPpyKgXhtSe+foN9250nDKXQHRkRZmzPXbNRZxrNUeXZCIfkfZ1RjofpxyGCDgabvnuaPBwIr7gFG1uQfiXAi3c+Bbg6VdwWIfe4rF/2PQ==;24:ItlP7h6WaS/QGNtRSCzxUjwRbAiWtAvowwXKV3QSQ6OV3EMrVMQznskowlrmgol64aPscWESj8zvt/H3iHgYL3yfcLR4WNKDcc8g1+Jb60E=;7:6fpdzQ27uav7dyp21HheL0OQ+8MVhLq+kA/o+P9gd7xZomavgLH/ra96Q3UB+q8ONgonl8PG3xqG3lt19+s2uJ7NSRgwJZRjeJSgAQW3ZAiof6lQ8pX1sbCBxv5iE+cjsbAjhsL7ks5wUsHPGXh+BhWdExXifvcBI+Y8he9u9AG4bFgrvHv3yFIpoBi5bJJbInO3jWFApe/JRfY5vnvppZYCcUOfOAlrZc6/SGfyaY8DRWz1dMXZepNY553ueG7L SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: hpe.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Aug 2016 17:36:28.1771 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: CS1PR84MB0311 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/08/2016 01:26 PM, Peter Zijlstra wrote: > On Mon, Jul 18, 2016 at 04:39:24PM -0400, Waiman Long wrote: >> @@ -302,22 +306,42 @@ static inline bool mutex_try_to_acquire(struct mutex *lock) >> * >> * Returns true when the lock was taken, otherwise false, indicating >> * that we need to jump to the slowpath and sleep. >> + * >> + * The waiter flag is set to true if the spinner is a waiter in the wait >> + * queue. As the waiter has slept for a while, it should have priority to >> + * get the lock over the regular spinners. So going to wait at the end of >> + * the OSQ isn't fair to the waiter. > If the OSQ lock were a full FIFO it would in fact be fair, but its not > and things can drop out the middle and go (back) to sleep. > > This has nothing to do with the end or not. Yes, the OSQ is not strictly FIFO, but the wait queue is. There is a much higher chance of lock starvation if the waiter is put at the end of the OSQ instead of in front of it. I will change the wordings to illustrate this fact. >> Instead, it will spin on the lock >> + * directly and concurrently with the spinner at the head of the OSQ, if >> + * present. > Note that this isn't starvation proof in any way. Patch 1 by itself isn't starvation-proof. Coupled with patch 3 that put the waiter-spinner in front of OSQ, we will have a much higher chance to avoid lock starvation. We can also completely block optimistic spinning if the waiter can't get the lock after a certain number of wakeup-sleep cycles, if the goal is to make it starvation proof. > >> There may be a bit more cacheline contention in this case. > This is relevant how ? It is just that there will be one more CPU contending on the lock cacheline. > >> + * The waiter also needs to set the lock to -1 instead of 0 on lock >> + * acquisition. > This is unrelated to the previous bits and thus should not be in the > same paragraph. Also, a 'why' would be more helpful. Will explain a bit more in the comments. Regards, Longman