From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
        id S1752571AbdCEDJH (ORCPT <rfc822;w@1wt.eu>);
        Sat, 4 Mar 2017 22:09:07 -0500
Received: from LGEAMRELO11.lge.com ([156.147.23.51]:49688 "EHLO
        lgeamrelo11.lge.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
        with ESMTP id S1752296AbdCEDJG (ORCPT
        <rfc822;linux-kernel@vger.kernel.org>);
        Sat, 4 Mar 2017 22:09:06 -0500
X-Original-SENDERIP: 156.147.1.151
X-Original-MAILFROM: byungchul.park@lge.com
X-Original-SENDERIP: 10.177.222.33
X-Original-MAILFROM: byungchul.park@lge.com
Date: Sun, 5 Mar 2017 12:08:45 +0900
From: Byungchul Park <byungchul.park@lge.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: mingo@kernel.org, tglx@linutronix.de, walken@google.com,
        boqun.feng@gmail.com, kirill@shutemov.name,
        linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        iamjoonsoo.kim@lge.com, akpm@linux-foundation.org, npiggin@gmail.com,
        kernel-team@lge.com, Michal Hocko <mhocko@kernel.org>,
        Nikolay Borisov <nborisov@suse.com>, Mel Gorman <mgorman@suse.de>
Subject: Re: [PATCH v5 06/13] lockdep: Implement crossrelease feature
Message-ID: <20170305030845.GA11100@X58A-UD3R>
References: <1484745459-2055-1-git-send-email-byungchul.park@lge.com>
 <1484745459-2055-7-git-send-email-byungchul.park@lge.com>
 <20170228134018.GK5680@worktop>
 <20170301054323.GE11663@X58A-UD3R>
 <20170301122843.GF6515@twins.programming.kicks-ass.net>
 <20170302134031.GG6536@twins.programming.kicks-ass.net>
 <20170303001737.GF28562@X58A-UD3R>
 <20170303081416.GT6515@twins.programming.kicks-ass.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20170303081416.GT6515@twins.programming.kicks-ass.net>
User-Agent: Mutt/1.5.21 (2010-09-15)
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Fri, Mar 03, 2017 at 09:14:16AM +0100, Peter Zijlstra wrote:
> On Fri, Mar 03, 2017 at 09:17:37AM +0900, Byungchul Park wrote:
> > On Thu, Mar 02, 2017 at 02:40:31PM +0100, Peter Zijlstra wrote:
> 
> > > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > > index a95e5d1..7baea89 100644
> > > --- a/kernel/locking/lockdep.c
> > > +++ b/kernel/locking/lockdep.c
> > > @@ -1860,6 +1860,17 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,
> > >  		}
> > >  	}
> > >  
> > > +	/*
> > > +	 * Is the <prev> -> <next> redundant?
> > > +	 */
> > > +	this.class = hlock_class(prev);
> > > +	this.parent = NULL;
> > > +	ret = check_noncircular(&this, hlock_class(next), &target_entry);
> > > +	if (!ret) /* exists, redundant */
> > > +		return 2;
> > > +	if (ret < 0)
> > > +		return print_bfs_bug(ret);
> > > +
> > >  	if (!*stack_saved) {
> > >  		if (!save_trace(&trace))
> > >  			return 0;
> > 
> > This whoud be very nice if you allow to add this code. However, prev_gen_id
> > thingy is still useful, the code above can achieve it though. Agree?
> 
> So my goal was to avoid prev_gen_id, and yes I think the above does
> that.
> 
> Now the problem with the above condition is that it makes reports
> harder to decipher, because by avoiding adding redundant links to our
> graph we loose a possible shorter path.

Let's see the following example:

   A -> B -> C

   where A, B and C are typical lock class.

Assume the graph above was built and operations happena in the
following order:

   CONTEXT X		CONTEXT Y
   ---------		---------
   acquire DX
			acquire A
			acquire B
			acquire C

			release and commit DX

   where A, B and C are typical lock class, DX is a crosslock class.

The graph will grow as following _without_ prev_gen_id.

        -> A -> B -> C
       /    /    /
   DX -----------

   where A, B and C are typical lock class, DX is a crosslock class.

The graph will grow as following _with_ prev_gen_id.

   DX -> A -> B -> C

   where A, B and C are typical lock class, DX is a crosslock class.

You said the former is better because it has smaller cost in bfs. But it
has to use _much_ more memory to keep additional nodes in graph. Without
exaggeration, every crosslock would get linked with all locks in history
locks, on commit, unless redundant. It might be pretty more than we
expect - I will check and let you know how many it is. Is it still good?