From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932594AbcHKPki (ORCPT ); Thu, 11 Aug 2016 11:40:38 -0400 Received: from mail-cys01nam02on0116.outbound.protection.outlook.com ([104.47.37.116]:62797 "EHLO NAM02-CY1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S932432AbcHKPkb (ORCPT ); Thu, 11 Aug 2016 11:40:31 -0400 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=waiman.long@hpe.com; Message-ID: <57AC9C64.7080500@hpe.com> Date: Thu, 11 Aug 2016 11:40:20 -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: Jason Low CC: Peter Zijlstra , Ingo Molnar , , , Jason Low , Davidlohr Bueso , Tim Chen , , "Paul E. McKenney" Subject: Re: [PATCH v2] locking/mutex: Prevent lock starvation when spinning is enabled References: <1470854648.17361.9.camel@j-VirtualBox> In-Reply-To: <1470854648.17361.9.camel@j-VirtualBox> Content-Type: text/plain; charset="UTF-8"; format=flowed Content-Transfer-Encoding: 7bit X-Originating-IP: [72.71.243.167] X-ClientProxiedBy: BLUPR08CA0042.namprd08.prod.outlook.com (10.141.200.22) To CS1PR84MB0309.NAMPRD84.PROD.OUTLOOK.COM (10.162.189.158) X-MS-Office365-Filtering-Correlation-Id: 56804423-7d96-4704-659a-08d3c1fdd24a X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0309;2:AclZOpI1OvGBDhPx46Mxqnbe/S2OAh3akiLJCpcBuKVWIA0MPkUT2JmYMIepeEjwjuEBIw8rpplDEro/kaAqFrVWgi7ZFWN+tFEmTKwcX/jRfZmkte3Xm+NMd9amiiwulfMBADbzaZbElJfDcfcFh2e7yE06Z7hEkqtygxloFIjng1IVIBAXoQ8ImLmOWQNO;3:w5ojCuWR2DPzUuGIgaR3PbwRX0nvoXY/jV4GelfEI2PVcUl1nXHG7uBr5cLZvJrYdbcwLLwr7XnWtbG1c/TCUp6x7kvqUHhcuN2yIo0I74v6L+oPaUWnecboRuZABriw X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:CS1PR84MB0309; X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0309;25:Oqk7NXo1/PFZv+JDIH5kNu0a8AGwzHttIvS6WVfdvRztKhx+8n68iZXRw1mWcazoq8HYmJ3J8+29jXOcw2BcthQEs4FS/DfZlrvq8SMD/p4sE0S6IuIw3CSy26sROi4/ZDy7TQUABEKHFVuTp8Fy/ausLe4yH6rwSET+UThMm94/ChdnoetaYp9K8ZsqDHkdxTx7m9HFXQCagTTjqlLnOl1UEovuTt/t07+AxsEvN9z9TZsjwOLmiMKGuZ3yPh4ky2WR1oQVGADBqkzYBY0ODa24C5p+TeO5nM6BBdu/UI4VRpEAYMZ9YRNtlYLf8+R398ysHv7/tjLsS50BOSUbXO71XyKufvNM9uoVN7ibIGiCBEKTt3f5vZq8GlpqsnQSVSCEBPyKj07fXBk4u6Olw5DOdqz/Dl+exJfnUC5cbpFZEPUcDOAvTrYfwevmKlaYhmq8E0DMJz/5isbV/N2lT4xCBUieTnrBDqpeJszb9/ZcvskTI28pKHzsRj6Yg02VbmafbuDgojlxUbN1jjJ+IwS99Ok3go6VumYiQ8gxoCwT+1EiaE8W0mfng2wir//ia0RG8446j4w1CBRKaIbW0BYOQqbpn2SlmgEU8/o+sXyTdXgVZxpIdXJQI1VLW/uDOOjMPyc5XD9nrCupMAwZ7d4zS9kWi2TdBLyb5xoH4C3aVSieqyMAMxB4Fqh4YxME1jF+y8gBxBeCFnN+BAy9FQ==;31:EwZ/bJt1fCqe73ET43Q42VkvXW5UA1n6Zos3Wnm5L58JiFYung8GKIIqNQTKwuRjwxF+fT1tWGYxgx73FLB2PfD7jugACnHPReQNUJt76rJB+OyS2axEh+ri0cz+fzTHh1jBWUTVFXjN+vxwPZEyzI67nB/pPuuc5XB15/VqG1MSmrGx7WvXzrnas7WSF66P2BILjBY01vfwymaPBeXUD4gjVhGl/i9i+c2E0BsZ5dY= X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0309;20:uFRD8iRa5kqpFxPBIrgL5kxh3BIYZHPl3fAcSUrNnIKen42bN4H4+ZM6+PmraMvUn6y7/lZm3LSrVX77EhpwYY8k1emOGGHIgNleVuN1ZVcB9EO3NmjaoE+t7L8AekWQfhxSM3tXkcs+9PX6d4G1WyYMUfKcnw0l6fnL3REbHA/s+rmjwIQcJL1uTM+evMwWXBVCHiUE0bC/VyXIxiQ4u2BtirIV4/din02yR+TYNcPgTOBdLnxjM+z9scnRpVrAtuyPPpnsf7iVgIzK7CDQh+G/nwJlS3mrSkzYDjfsc8THJxzdxzAmx6/h39sVm3LgfE6jQwmJMf9ATmmcwVf0VyLEDf1a1xIWo9YmIjyupfFbiQrrImUh59DyvUwD2MBF3DYeZSctdei1NYCUfPsZ3c3hSr3yCfbIiar7ZSEG0SvUWw2W6Rqiz1X+DzuKNQ/MomqOIyIzEvzpFg/Qa7nv5iFlx8NLwEySvY2Va4XggouHdqdEqDS+S5Bq0ha8Rs0b X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(227479698468861)(228905959029699); X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001)(6055026);SRVR:CS1PR84MB0309;BCL:0;PCL:0;RULEID:;SRVR:CS1PR84MB0309; X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0309;4:IhOKjep6bAT2l8X17u5TebuDtRMEpw+HewYbucP9256B7aQcEJ9B+E3ZgVZg0MBErLstOcZmdw9cfgg6xteA7SMQX/C6E4+/n3KCuo7jR4sgn0fnPXPltHDP0xnzGoFsz+key1mnycxHbjWAwrAdmPJRUo7llgQuYJfZSAuDzBJI3b4MPX3GYpzNvk8Ip5Tr/qxnufxyfyHk45VcgnUZgGq5w7orjWXYZeuTbYZUXroqjjpp7vNyzuLCfdhZcYVPBYF1q5Vmv7LB6pzlIfxRTyOU7nHobfpYDeObDxgL81BQSWHKThRTsLETpM6mFDd7oxhXes+edTkEGlynKX3S1kKXVUzxgOKyZEKXjHT/+PK7bYuNCzNH5InClpuRmeJwJjuntj6mTCQ8/gF/oSGzBaPCXO80WmwG/Onw7Ne4dnTVZno+yrsbebWQbSdCwf5eV4jIkBxYZhNYg6M4W8hmIg== X-Forefront-PRVS: 0031A0FFAF X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6049001)(6009001)(7916002)(199003)(24454002)(377454003)(189002)(81166006)(4326007)(50986999)(101416001)(3846002)(6116002)(586003)(77096005)(81156014)(76176999)(59896002)(7736002)(8666005)(50466002)(2906002)(230700001)(65816999)(54356999)(87266999)(42186005)(7846002)(305945005)(19580405001)(8676002)(80316001)(64126003)(19580395003)(66066001)(106356001)(68736007)(83506001)(117156001)(36756003)(105586002)(92566002)(189998001)(110136002)(33656002)(23676002)(97736004)(4001350100001)(65956001)(86362001)(65806001)(2950100001)(47776003)(7059030);DIR:OUT;SFP:1102;SCL:1;SRVR:CS1PR84MB0309;H:[192.168.142.185];FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtDUzFQUjg0TUIwMzA5OzIzOlpSaUFkRGd1VVdydjdLZEo2SWgxaSswanpU?= =?utf-8?B?aVJUTjluK1BTbTlwOS9hbmZPVEtVT1BhcFVpNFUyYjl0MEtpTG9VclVEeGFH?= =?utf-8?B?cDdtWWJPLzBITytrNFFlOWVEWHhRam1aajgybkE3ZG1WSWw0eW9jU09sSUJ4?= =?utf-8?B?ZzNPejFTMGwvWGFUOHh5eWs3OU5BV1MzWUxXM1BUSTFObzN4eDJ4R2Rha29S?= =?utf-8?B?eDFsNnZ6N1VJWVhNaUxLM3g3ZHR5ZzdyTGtaRVMzRkR2WHVHWVc1aitwdUtz?= =?utf-8?B?MXRPbmlkdDRkREV1RkpXQzBOOWo4TmNHdjZkSnprZWNmd3NJTERFRDNpdXFW?= =?utf-8?B?M1RneFRqS0p3SUxRU2FzV29RZTZTUGd4Vnd6ME5jeXN5bmFBeERzSW1rTCtl?= =?utf-8?B?NW92WmxpL29rN09rTDJwZE1VY01VRWVFMmhkTWZ0S1JZa2JBVlpaRnB0MnI5?= =?utf-8?B?VTdVUDVxQ0ExOVU3R2c4K2lpQTNyWjh1QmtNZTJ6ZVNQckJOclBuR0lWM0Yr?= =?utf-8?B?STc4NEF4OTZFUkw2dFRYeFNyYzBCNEJNZ1NzSXQ4eWRRcUZidkZaVU0zY0w5?= =?utf-8?B?SXNHVnlkVmhGWUtYMUNWTWxLZlRzcmQ4c01pOEdwZWc1bnJNd3dKMTRqcjA0?= =?utf-8?B?VWw4eHJzNlcxMWlWcFBJM2FoWXEwRnNmRkJldzZCOHBCN3BmV2o4LzRmZ0s0?= =?utf-8?B?bVFrUTdObnZxd3V3eDdsQmN5cjZPdGNNWWxwQjZtL3BsNFRkWUUrdkRQaXVz?= =?utf-8?B?U3A1WFZnSFJrMExPRHJFbThCRWM3SmFFeUxQZEd3NEQzbGViaE1SQ2I5dFJx?= =?utf-8?B?dlRlZS9nVzBDdEhSOUFVU0pDbTdnRGwrWW1TMXZobjl2RXZhMnNwMk1OUm9u?= =?utf-8?B?T0xtdlNsWDk4eEM5a1B2WGRqUVZrTW9jTnBGcEVJMEl4bHJqR2tHRi9scHVp?= =?utf-8?B?STBRbDEwV2FKamNIS3I5UlhjRHhjTDBuQ3RBUmI4VEJ3QUF6VkF4V1R6TzhR?= =?utf-8?B?NWpXdlB4cU95SkVHN0szbmdkdGN4cGdveVBRVklLWXNIeHA0dmI0a2FFZCtM?= =?utf-8?B?eWxJdTRXVG1ra3NaTnlOelJFVnVucGhFb3ltOHRLejQ1RnU4NERFMVliYTFn?= =?utf-8?B?V2ZKQWIwUHc0d2t5OFhXbG1SSzNzd3l5b2QyckV3c05XTUFuaUJjZHFCKzY4?= =?utf-8?B?akJZTkJHdlhpK1Yrb2pLbXZEWHc1bzZHZnBsOXpuQnNoWFNQZWxKZncrbkNQ?= =?utf-8?B?VFNBNVVac3E3R29ZWEJTK29ZekFKOCt4bUdaV3ZwYmthV0Irb0trQUxwcTlS?= =?utf-8?B?UjNHUVlPemV4aG1Rd1lKd2Nwb0Z0K2gwQjBLcTNEenErK0NGMnR2SmRrbEE0?= =?utf-8?B?KzcyMzdSRnFTR0VRa292eUV2a280SjE2YmdiTE56ZW9WRkszUUVIUmJiNWIy?= =?utf-8?B?VDdFQmxIdS9yUW01VUtZRHkwV1dUUkVtVTVCWnJtQlRYaEpYT3pUNjZUeUo3?= =?utf-8?B?Q0h3djg3cTBrZmNFZHpOdW9ZS3k0N29zR2FDVEtvdzBkd0RIdU83WTJKa3VK?= =?utf-8?B?VHhpbTFLTXBTN1NoaDh5WjFQMW54bUMvQnU1U0dtK0liVW5oWDNjM2lQUnk4?= =?utf-8?B?SnAwY3cvdURTTHJuT05kQkw5VStqUmxPMERETnczUTVXTFo2dWV4Z3IwMWlO?= =?utf-8?B?ZVFiMzRjcDVWaFdlbVhnV1JYNEZmKzJESkpBMExuSVY3OUpXQ0o3aG9VbzBE?= =?utf-8?B?NjZ1cjdNcnJlQkJLdGNTOVBFSWRGelpVRUNhdlI5dDE0Nnc4cTkrVXk1QUpY?= =?utf-8?B?Sm1IbXVwWlA2d0RSYVFaYVdzTFlRRHYwenJ3NTM0R1UzY2c9PQ==?= X-Microsoft-Exchange-Diagnostics: 1;CS1PR84MB0309;6:F+whREO1sIlTF8uX31D8lrLVQdqqXqRvKgbRFKb3JP+2Uu7h/rGJPkuwgkK5RhYEiuKpIeMoKAiMVldj//0xlbwLcEwfDWenxbYDphKCLeW2pAUkNVPFtZePYMd3ptcfeThf4UFNgooueGVKKlvcR6xf0paMEEgqM1aR/8eg3ovDNvzN1Lj9XKkok5csEJkQOEiGkJUpuaCq9SQdLglUD/OpgUgA144CGMsK5POchrshGfgM2YY8Hkr0iXagWmtQ9Fdi96VYAKYAs4QwujQVU6YzrmEtSwh+jY1ZxsMxp//PSMYaBftGzd1K8UzByVtcxMJ7NseIeIMIy+oJhpyW5g==;5:QXz6W5CqNtN8EgIime3cqd4+5n+HUt3f9WzDVanr00m3/bhYZ/kt8zlKdoeYR5XXjxTdWw65MEpn3Hw18SdQIao9YOuQi99dDl9/bYPcdmhBcrmkQMENcDCE93bidj8x4ssivl6xsZvSlTs7vevF2g==;24:tZEsn7C2JK4REU7OcW1Kut9QV+IE5F4KPwYh0NY170MABSDU9IuRFw57xrGPS05+Du4avg4RNy/vGivVItwpSj0aNh6VcjaeVn1V3PwFjEU=;7:DqQroQNzxNN8xjMe3nLDWQpoRROFXez56NuDuwl9GRauXRIjvVjFR4gAU64ZVOGxBsm5yt9r5U9pV3afRXX/p6UK7kwAzbgMXExYCbyJD2dfVkLWAH65PvS/6lBz9X5cNGOqL9oY9w8rQZRmK0aa9Y5HkpzmUQht9Kr5tfIzFPhXVBLneVFApQcS8NkKr85Z7kvINL9ASh2PFxh2nOQpIpoPOpkX5kfc/PGHL8ws8xWo5+VSI5jiq47RKhPUfXdP SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: hpe.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 11 Aug 2016 15:40:27.5057 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: CS1PR84MB0309 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/10/2016 02:44 PM, Jason Low wrote: > Imre reported an issue where threads are getting starved when trying > to acquire a mutex. Threads acquiring a mutex can get arbitrarily delayed > sleeping on a mutex because other threads can continually steal the lock > in the fastpath and/or through optimistic spinning. > > Waiman has developed patches that allow waiters to return to optimistic > spinning, thus reducing the probability that starvation occurs. However, > Imre still sees this starvation problem in the workloads when optimistic > spinning is disabled. > > This patch adds an additional boolean to the mutex that gets used in > the CONFIG_SMP&& !CONFIG_MUTEX_SPIN_ON_OWNER cases. The flag signifies > whether or not other threads need to yield to a waiter and gets set > when a waiter spends too much time waiting for the mutex. The threshold > is currently set to 16 wakeups, and once the wakeup threshold is exceeded, > other threads must yield to the top waiter. The flag gets cleared > immediately after the top waiter acquires the mutex. > > This prevents waiters from getting starved without sacrificing much > much performance, as lock stealing is still allowed and only > temporarily disabled when it is detected that a waiter has been waiting > for too long. > > Reported-by: Imre Deak > Signed-off-by: Jason Low > --- > v1->v2: > - Addressed Waiman's suggestions of needing the yield_to_waiter > flag only in the CONFIG_SMP case. > > - Make sure to only clear the flag if the thread is the top waiter. > > - Refactor code to clear flag into an inline function. > > - Rename 'loops' variable name to 'wakeups'. > > include/linux/mutex.h | 2 ++ > kernel/locking/mutex.c | 83 +++++++++++++++++++++++++++++++++++++++++++------- > 2 files changed, 74 insertions(+), 11 deletions(-) > > diff --git a/include/linux/mutex.h b/include/linux/mutex.h > index 2cb7531..5643a233 100644 > --- a/include/linux/mutex.h > +++ b/include/linux/mutex.h > @@ -57,6 +57,8 @@ struct mutex { > #endif > #ifdef CONFIG_MUTEX_SPIN_ON_OWNER > struct optimistic_spin_queue osq; /* Spinner MCS lock */ > +#elif defined(CONFIG_SMP) > + bool yield_to_waiter; /* Prevent starvation when spinning disabled */ > #endif > #ifdef CONFIG_DEBUG_MUTEXES > void *magic; > diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c > index a70b90d..faf31a0 100644 > --- a/kernel/locking/mutex.c > +++ b/kernel/locking/mutex.c > @@ -55,6 +55,8 @@ __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); > +#elif defined(CONFIG_SMP) > + lock->yield_to_waiter = false; > #endif > > debug_mutex_init(lock, name, key); > @@ -71,6 +73,9 @@ EXPORT_SYMBOL(__mutex_init); > */ > __visible void __sched __mutex_lock_slowpath(atomic_t *lock_count); > > + > +static inline bool need_yield_to_waiter(struct mutex *lock); > + > /** > * mutex_lock - acquire the mutex > * @lock: the mutex to be acquired > @@ -99,7 +104,10 @@ void __sched mutex_lock(struct mutex *lock) > * The locking fastpath is the 1->0 transition from > * 'unlocked' into 'locked' state. > */ > - __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath); > + if (!need_yield_to_waiter(lock)) > + __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath); > + else > + __mutex_lock_slowpath(&lock->count); > mutex_set_owner(lock); > } > > @@ -398,12 +406,51 @@ done: > > return false; > } > + > +static inline void do_yield_to_waiter(struct mutex *lock, int *wakeups) > +{ > + return; > +} > + > +static inline void clear_yield_to_waiter(struct mutex *lock) > +{ > + return; > +} > + > +static inline bool need_yield_to_waiter(struct mutex *lock) > +{ > + return false; > +} > + > #else > static bool mutex_optimistic_spin(struct mutex *lock, > struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx) > { > return false; > } > + > +#define MUTEX_WAKEUP_THRESHOLD 16 > + > +static inline void do_yield_to_waiter(struct mutex *lock, int *wakeups) > +{ > + *wakeups += 1; > + > + if (*wakeups< MUTEX_WAKEUP_THRESHOLD) > + return; > + > + if (lock->yield_to_waiter != true) > + lock->yield_to_waiter = true; > +} > + > +static inline void clear_yield_to_waiter(struct mutex *lock) > +{ > + lock->yield_to_waiter = false; > +} > + > +static inline bool need_yield_to_waiter(struct mutex *lock) > +{ > + return lock->yield_to_waiter; > +} > #endif > > _ The *yield* helper functions should be in a separate conditional compilation block as the declaration of yield_to_waiter may not match the helper functions with certain combination of config variables. Something like #if !defined(CONFIG_MUTEX_SPIN_ON_OWNER) && defined(CONFIG_SMP) ... #else ... #endif Cheers, Longman