Re: [RFC tip/locking/lockdep v5 04/17] lockdep: Introduce lock_list::dep

Boqun Feng
2018-02-26T10:12:01Z

[-- Attachment #1: Type: text/plain, Size: 2782 bytes --]

On Mon, Feb 26, 2018 at 10:00:50AM +0100, Peter Zijlstra wrote:
> 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 :-(
>

Take care!

> 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.

I think that works, will apply this simplification to see whether the
self tests agree.

Btw, given the comments in the code, I think it's better to name
"have_xr" as "only_xr"? I have a feeling that my comment-less code
somehow misled you to that name ;-(

Regards,
Boqun

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]