From patchwork Tue Apr 30 18:45:48 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Vetter X-Patchwork-Id: 16547 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-yh0-f72.google.com (mail-yh0-f72.google.com [209.85.213.72]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 0F18020065 for ; Tue, 30 Apr 2013 18:43:24 +0000 (UTC) Received: by mail-yh0-f72.google.com with SMTP id f35sf1395668yha.3 for ; Tue, 30 Apr 2013 11:43:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ffwll.ch; s=google; h=x-received:x-beenthere:x-received:received-spf:x-received :x-forwarded-to:x-forwarded-for:delivered-to:x-received:received-spf :x-received:from:to:date:message-id:x-mailer:in-reply-to:references :cc:subject:x-beenthere:x-mailman-version:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:list-subscribe :mime-version:errors-to:sender:x-original-sender :x-original-authentication-results:mailing-list:x-google-group-id :content-type:content-transfer-encoding; bh=lZJrWNrIjj4vI6InnQhPLKqwpZzsDTlFIz9rQaugWu0=; b=QqOmMIulLMx4pge/t2v6bqX2aUZomdiMoXvLxN+5uzcwPAJH1ZzDjwIF725SYqGbae JjiSLC5WkCGsbFrtEiuUmybjcqPF9Y/VdmVT3JdOOQlSTp3zhVCIYtxJXxQDMkY2CYhy LZ90uo9QrLNvD6dBauidXaUex39/Smo7JK330= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-received:x-beenthere:x-received:received-spf:x-received :x-forwarded-to:x-forwarded-for:delivered-to:x-received:received-spf :x-received:from:to:date:message-id:x-mailer:in-reply-to:references :cc:subject:x-beenthere:x-mailman-version:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:list-subscribe :mime-version:errors-to:sender:x-gm-message-state:x-original-sender :x-original-authentication-results:mailing-list:x-google-group-id :content-type:content-transfer-encoding; bh=lZJrWNrIjj4vI6InnQhPLKqwpZzsDTlFIz9rQaugWu0=; b=Mqk5G6tEZEsiUWJSTKkMrng3Lr03LhY17RtfRCoyT5MCpMUzgSndVF+s56g1FVo2wL PP8QPH62AqlcJW0+6Dluq1VXcgTjeqNsukC44fC15i+9ddv8gUyKaO4uqaoiPES18JJG drB6J4ZpMSqAF7eR1pZAuKD0ajZieGTD8ZHYHuOXrV8iIDdsbCzPll0uTHprNszXnMWL U6jnNj5ppmK4uRoHQ2Smzky9V8J7Knbc17znyJb+IngrCvljsKY8O6v/EhTrswvk09aW tOimwSSkvpVxbDyhqYueuHLqA1HMk38DKFZMasW/5RbmYNHo5z2MOd8fJAsCk5iXafQA kOdg== X-Received: by 10.58.172.66 with SMTP id ba2mr4645061vec.32.1367347399816; Tue, 30 Apr 2013 11:43:19 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.49.58.172 with SMTP id s12ls406595qeq.18.gmail; Tue, 30 Apr 2013 11:43:19 -0700 (PDT) X-Received: by 10.52.29.19 with SMTP id f19mr29995924vdh.100.1367347399378; Tue, 30 Apr 2013 11:43:19 -0700 (PDT) Received: from mail-vc0-f169.google.com (mail-vc0-f169.google.com [209.85.220.169]) by mx.google.com with ESMTPS id sc6si12592928vdc.138.2013.04.30.11.43.19 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 30 Apr 2013 11:43:19 -0700 (PDT) Received-SPF: neutral (google.com: 209.85.220.169 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=209.85.220.169; Received: by mail-vc0-f169.google.com with SMTP id gd11so731811vcb.28 for ; Tue, 30 Apr 2013 11:43:19 -0700 (PDT) X-Received: by 10.52.228.71 with SMTP id sg7mr29127126vdc.51.1367347399149; Tue, 30 Apr 2013 11:43:19 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patches@linaro.org Received: by 10.58.127.98 with SMTP id nf2csp120006veb; Tue, 30 Apr 2013 11:43:18 -0700 (PDT) X-Received: by 10.180.108.3 with SMTP id hg3mr26572289wib.17.1367347396670; Tue, 30 Apr 2013 11:43:16 -0700 (PDT) Received: from ip-10-141-164-156.ec2.internal (lists.linaro.org. [54.225.227.206]) by mx.google.com with ESMTPS id g47si2431513eem.27.2013.04.30.11.43.14 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Tue, 30 Apr 2013 11:43:16 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linaro-mm-sig-bounces@lists.linaro.org designates 54.225.227.206 as permitted sender) client-ip=54.225.227.206; Received: from localhost ([127.0.0.1] helo=ip-10-141-164-156.ec2.internal) by ip-10-141-164-156.ec2.internal with esmtp (Exim 4.76) (envelope-from ) id 1UXFVD-0001yt-EI; Tue, 30 Apr 2013 18:42:11 +0000 Received: from mail-wi0-f181.google.com ([209.85.212.181]) by ip-10-141-164-156.ec2.internal with esmtp (Exim 4.76) (envelope-from ) id 1UXFVB-0001yo-R6 for linaro-mm-sig@lists.linaro.org; Tue, 30 Apr 2013 18:42:10 +0000 Received: by mail-wi0-f181.google.com with SMTP id c10so882655wiw.8 for ; Tue, 30 Apr 2013 11:43:03 -0700 (PDT) X-Received: by 10.194.71.241 with SMTP id y17mr12508513wju.31.1367347383152; Tue, 30 Apr 2013 11:43:03 -0700 (PDT) Received: from phenom.ffwll.local (178-83-130-250.dynamic.hispeed.ch. [178.83.130.250]) by mx.google.com with ESMTPSA id m14sm2829398wij.9.2013.04.30.11.43.00 for (version=TLSv1.2 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 30 Apr 2013 11:43:01 -0700 (PDT) From: Daniel Vetter To: LKML Date: Tue, 30 Apr 2013 20:45:48 +0200 Message-Id: <1367347549-8022-1-git-send-email-daniel.vetter@ffwll.ch> X-Mailer: git-send-email 1.7.10.4 In-Reply-To: <20130428165914.17075.57751.stgit@patser> References: <20130428165914.17075.57751.stgit@patser> Cc: linux-arch@vger.kernel.org, peterz@infradead.org, x86@kernel.org, dri-devel@lists.freedesktop.org, linaro-mm-sig@lists.linaro.org, robclark@gmail.com, rostedt@goodmis.org, daniel@ffwll.ch, tglx@linutronix.de, mingo@elte.hu, linux-media@vger.kernel.org Subject: [Linaro-mm-sig] [PATCH] [RFC] mutex: w/w mutex slowpath debugging X-BeenThere: linaro-mm-sig@lists.linaro.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: linaro-mm-sig-bounces@lists.linaro.org Sender: linaro-mm-sig-bounces@lists.linaro.org X-Gm-Message-State: ALoCoQlJ7r7iFZ/+/K16x6/TM2a4eI8hyY7skUQH4BDjRCVJgHEWH+qCl4utSGYav9sHUBgWwwam X-Original-Sender: daniel.vetter@ffwll.ch X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 209.85.220.169 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org; dkim=neutral (bad format) header.i=@ffwll.ch Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 Injects EDEADLK conditions at pseudo-random interval, with exponential backoff up to UINT_MAX (to ensure that every lock operation still completes in a reasonable time). This way we can test the wound slowpath even for ww mutex users where contention is never expected, and the ww deadlock avoidance algorithm is only needed for correctness against malicious userspace. An example would be protecting kernel modesetting properties, which thanks to single-threaded X isn't really expected to contend, ever. I've looked into using the CONFIG_FAULT_INJECTION infrastructure, but decided against it for two reasons: - EDEADLK handling is mandatory for ww mutex users and should never affect the outcome of a syscall. This is in contrast to -ENOMEM injection. So fine configurability isn't required. - The fault injection framework only allows to set a simple probability for failure. Now the probability that a ww mutex acquire stage with N locks will never complete (due to too many injected EDEADLK backoffs) is zero. But the expected number of ww_mutex_lock operations for the completely uncontended case would be O(exp(N)). The per-acuiqire ctx exponential backoff solution choosen here only results in O(log N) overhead due to injection and so O(log N * N) lock operations. This way we can fail with high probability (and so have good test coverage even for fancy backoff and lock acquisition paths) without running into patalogical cases. Note that EDEADLK will only ever be injected when we managed to acquire the lock. This prevents any behaviour changes for users which rely on the EALREADY semantics. Signed-off-by: Daniel Vetter --- include/linux/mutex.h | 8 ++++++++ kernel/mutex.c | 31 +++++++++++++++++++++++++++++++ lib/Kconfig.debug | 10 ++++++++++ 3 files changed, 49 insertions(+) diff --git a/include/linux/mutex.h b/include/linux/mutex.h index 004f863..82d56ec 100644 --- a/include/linux/mutex.h +++ b/include/linux/mutex.h @@ -93,6 +93,10 @@ struct ww_acquire_ctx { #ifdef CONFIG_DEBUG_LOCK_ALLOC struct lockdep_map dep_map; #endif +#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH + unsigned deadlock_inject_interval; + unsigned deadlock_inject_countdown; +#endif }; struct ww_mutex { @@ -278,6 +282,10 @@ static inline void ww_acquire_init(struct ww_acquire_ctx *ctx, &ww_class->acquire_key, 0); mutex_acquire(&ctx->dep_map, 0, 0, _RET_IP_); #endif +#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH + ctx->deadlock_inject_interval = ctx->stamp & 0xf; + ctx->deadlock_inject_countdown = ctx->deadlock_inject_interval; +#endif } /** diff --git a/kernel/mutex.c b/kernel/mutex.c index 66807c7..1cc3487 100644 --- a/kernel/mutex.c +++ b/kernel/mutex.c @@ -827,6 +827,35 @@ int __sched mutex_trylock(struct mutex *lock) EXPORT_SYMBOL(mutex_trylock); #ifndef CONFIG_DEBUG_LOCK_ALLOC + +#ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH +static int __sched +ww_mutex_deadlock_injection(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) +{ + if (ctx->deadlock_inject_countdown-- == 0) { + tmp = ctx->deadlock_inject_interval; + if (tmp > UINT_MAX/4) + tmp = UINT_MAX; + else + tmp = tmp*2 + tmp + tmp/2; + + ctx->deadlock_inject_interval = tmp; + ctx->deadlock_inject_countdown = tmp; + + ww_mutex_unlock(lock); + + return -EDEADLK; + } + + return 0; +} +#else +static int __sched +ww_mutex_deadlock_injection(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) +{ + return 0; +} +#endif int __sched ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) { @@ -839,6 +868,7 @@ ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) if (likely(!ret)) { ww_mutex_set_context_fastpath(lock, ctx); mutex_set_owner(&lock->base); + return ww_mutex_deadlock_injection(lock, ctx); } else ret = __ww_mutex_lock_slowpath(lock, ctx); return ret; @@ -857,6 +887,7 @@ ww_mutex_lock_interruptible(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) if (likely(!ret)) { ww_mutex_set_context_fastpath(lock, ctx); mutex_set_owner(&lock->base); + return ww_mutex_deadlock_injection(lock, ctx); } else ret = __ww_mutex_lock_interruptible_slowpath(lock, ctx); return ret; diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 28be08c..8c41f73 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -547,6 +547,16 @@ config DEBUG_MUTEXES This feature allows mutex semantics violations to be detected and reported. +config DEBUG_WW_MUTEX_SLOWPATH + bool "Wait/wound mutex debugging: Slowpath testing" + depends on DEBUG_KERNEL + help + This feature enables slowpath testing for w/w mutex users by + injecting additional -EDEADLK wound/backoff cases. Together with + the full mutex checks enabled with (CONFIG_PROVE_LOCKING) this + will test all possible w/w mutex interface abuse with the + exception of simply not acquiring all the required locks. + config DEBUG_LOCK_ALLOC bool "Lock debugging: detect incorrect freeing of live locks" depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT && LOCKDEP_SUPPORT