linux-kernel - Re: [RFC tip/locking/lockdep v5 04/17] lockdep: Introduce lock

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20180226090050.GE25201@hirez.programming.kicks-ass.net>
Date:   Mon, 26 Feb 2018 10:00:50 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     Boqun Feng <boqun.feng@...il.com>
Cc:     linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
        Andrea Parri <parri.andrea@...il.com>
Subject: Re: [RFC tip/locking/lockdep v5 04/17] lockdep: Introduce
 lock_list::dep

On Sat, Feb 24, 2018 at 05:26:52PM +0800, Boqun Feng wrote:
> > This is for case like:
> > 
> > 	TASK1:
> > 		read_lock(A);
> > 		read_lock(B);
> > 	
> > 	TASK2:
> > 		write_lock(B);
> > 		read_lock(C);
> > 	
> > 	TASK3:
> > 		read_lock(B);
> > 		write_lock(C);
> > 
> > 	TASK4:
> > 		read_lock(C);
> > 		write_lock(A);
> > 
> > , which is not a deadlock.
> > 
> 
> After TASK 1,2,3 have executed, we have A -(RR)-> B, B -(RN/NR)-> C, and
> when TASK4 executed, we will try to add C -(RN)-> A into the graph.
> Before that we need to check whether we have a A -> ... -(*N)-> C path
> in the graph already, so we search from A (@prev is C and @this is A):
> 
> *	we set A->have_xr to false, because the dependency we are adding
> 	is a RN.
> 
> *	we find A -(RR)-> B, and since have_xr (= A->have_xr) is false,
> 	we can pick this dependency, and since for A -> B, we only have
> 	RR, so we set B->have_xr to true.
> 
> *	we then find B -(RN/NR)-> C, and since have_xr (= B->have_xr) is
> 	true, we will pick it only only_rx(C->dep) return false,
> 	otherwise we skip. Because we have RN and NR for B -> C,
> 	therefore we won't skip B -> C.
> 
> *	Now we try to set C->have_xr, if we set it to only_xr(C->dep),
> 	we will set it to false, right? Because B -> C has RN.
> 
> *	Since we now find a entry equal to @prev, we go into the
> 	hlock_conflict() logic and for expression
> 		
> 		hlock->read != 2 || !entry->have_xr 
> 	
> 	@hlock is the C in TASK4, so hlock->read == 2, and @entry is the
> 	C whose ->have_xr we just set, so entry->have_xr is false.
> 	Therefore hlock_conflict() returns true. And that indicates we
> 	find a deadlock in the search. But the above senario can not
> 	introduce a deadlock.
> 
> Could this help you, or I miss something?

Yes, although it took me forever to grasp because I have snot for brains
atm :-(

Would something like:


	dep = entry->dep;

	/* Mask out all *R -> R* relations. */
	if (have_xr)
		dep &= ~(RR_MASK | RN_MASK);

	/* If nothing left, we're done. */
	if (!dep)
		continue;

	/* If there are (only) *R left, set that for the next step. */
	entry->have_xr = !(dep & (RN_MASK | NN_MASK));


Work? I think that reads fairly simple.