From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.3 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_PASS, USER_AGENT_MUTT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1D508C282DB for ; Mon, 21 Jan 2019 09:12:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id E17712085A for ; Mon, 21 Jan 2019 09:12:51 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="EGKm2UYC" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727584AbfAUJMt (ORCPT ); Mon, 21 Jan 2019 04:12:49 -0500 Received: from bombadil.infradead.org ([198.137.202.133]:36054 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726030AbfAUJMt (ORCPT ); Mon, 21 Jan 2019 04:12:49 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=In-Reply-To:Content-Type:MIME-Version :References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=KpHvtGLe3TO/MAA4QbViAq/RTeqdnX0hHaBVCNw+17A=; b=EGKm2UYC4ys8l0z7sxdINw5qu 1pwMfzKu5/U2aNF27oLkg3E6THSIL9HHQi8y8tuziatJBvbQZIG36JUWRLFs7MU4oiil9i8mzQA9e bYjNnTCnzibh45fsV5l6VGvm1VVmLCuTOf3uPzWsl5fhTGZgSmFxvq8l/3D2V/9kGmbezail5kItO peDR18mF3P1+tOIYNJfWoZB44PLYuI07dcFavDFjMHQBIUPOuY7W7xUBaC7ilWN1nDTNY6ZnmNbU3 +FHcyvFSkqR4I3xZuB/Q/EVggMDjoztEoH21AXcfRfaBpnPi3k12Jta5x1IeFluXxMVyNkzQpBysI Ydlko91QA==; Received: from j217100.upc-j.chello.nl ([24.132.217.100] helo=hirez.programming.kicks-ass.net) by bombadil.infradead.org with esmtpsa (Exim 4.90_1 #2 (Red Hat Linux)) id 1glVdE-0005CJ-Qh; Mon, 21 Jan 2019 09:12:37 +0000 Received: by hirez.programming.kicks-ass.net (Postfix, from userid 1000) id 4F9A72846C71D; Mon, 21 Jan 2019 10:12:34 +0100 (CET) Date: Mon, 21 Jan 2019 10:12:34 +0100 From: Peter Zijlstra To: Waiman Long Cc: Ingo Molnar , Will Deacon , Thomas Gleixner , Borislav Petkov , "H. Peter Anvin" , linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org, x86@kernel.org, Zhenzhong Duan , James Morse , SRINIVAS Subject: Re: [PATCH 1/5] locking/qspinlock: Safely handle > 4 nesting levels Message-ID: <20190121091234.GG27931@hirez.programming.kicks-ass.net> References: <1548038994-30073-1-git-send-email-longman@redhat.com> <1548038994-30073-2-git-send-email-longman@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1548038994-30073-2-git-send-email-longman@redhat.com> User-Agent: Mutt/1.10.1 (2018-07-13) Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sun, Jan 20, 2019 at 09:49:50PM -0500, Waiman Long wrote: > +/** > + * acquire_lock_no_node - acquire lock without MCS node > + * @lock: Pointer to queued spinlock structure > + * > + * It is extremely unlikely that this function will ever be called. > + * Marking it as noinline to not mess with the slowpath code. This > + * function is for native qspinlock only. The PV qspinlock code has > + * its own simpler version. > + * > + * ----- ----- | ---- ----- ----- > + * |Tail2| <- ... |Head2| | |Node| <- |Tail1| <- ... |Head1| > + * ----- ----- | ---- ----- ----- > + * | | > + * V V > + * Spin on waiting Spin on locked > + * > + * The waiting and the pending bits will be acquired first which are now > + * used as a separator for the disjointed queue shown above. > + * > + * The current CPU will then be inserted into queue by placing a special > + * _Q_TAIL_WAITING value into the tail and makes the current tail > + * point to its own local node. The next incoming CPU will see the special > + * tail, but it has no way to find the node. Instead, it will spin on the > + * waiting bit. When that bit is cleared, it means that all the the > + * previous CPUs in the queue are gone and current CPU is the new lock > + * holder. I know it's monday morning and I've not had wake-up juice yet, but I don't think that's true. Consider there being two CPUs that ran out of nodes and thus we have two tail fragments waiting on the one waiting bit. There is no sane wait to recover from this.. and stay fair, why are we trying? That is; what's the problem with the below? Yes it sucks, but it is simple and doesn't introduce 100+ lines of code that 'never' gets used. --- diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c index 8a8c3c208c5e..983b49a75826 100644 --- a/kernel/locking/qspinlock.c +++ b/kernel/locking/qspinlock.c @@ -412,6 +412,12 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) idx = node->count++; tail = encode_tail(smp_processor_id(), idx); + if (idx >= MAX_NODES) { + while (!queued_spin_trylock(lock)) + cpu_relax(); + goto release; + } + node = grab_mcs_node(node, idx); /*