RE: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

> -Original Message-
> From: Peter Zijlstra [mailto:pet...@infradead.org]
> Sent: Friday, May 19, 2017 7:30 PM
> To: Byungchul Park
> Cc: mi...@kernel.org; t...@linutronix.de; wal...@google.com;
> boqun.f...@gmail.com; kir...@shutemov.name; linux-kernel@vger.kernel.org;
> linux...@kvack.org; iamjoonsoo@lge.com; a...@linux-foundation.org;
> wi...@infradead.org; npig...@gmail.com; kernel-t...@lge.com
> Subject: Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature
> 
> On Fri, May 19, 2017 at 05:07:08PM +0900, Byungchul Park wrote:
> > On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > > Lockdep is a runtime locking correctness validator that detects and
> > > reports a deadlock or its possibility by checking dependencies between
> > > locks. It's useful since it does not report just an actual deadlock
> but
> > > also the possibility of a deadlock that has not actually happened yet.
> > > That enables problems to be fixed before they affect real systems.
> > >
> > > However, this facility is only applicable to typical locks, such as
> > > spinlocks and mutexes, which are normally released within the context
> in
> > > which they were acquired. However, synchronization primitives like
> page
> > > locks or completions, which are allowed to be released in any context,
> > > also create dependencies and can cause a deadlock. So lockdep should
> > > track these locks to do a better job. The 'crossrelease'
> implementation
> > > makes these primitives also be tracked.
> >
> > Excuse me but I have a question...
> >
> > Only for maskable irq, can I assume that hardirq are prevented within
> > hardirq context? I remember that nested interrupts were allowed in the
> > past but not recommanded. But what about now? I'm curious about the
> > overall direction of kernel and current status. It would be very
> > appriciated if you answer it.
> 
> So you're right. In general enabling IRQs from hardirq context is
> discouraged but allowed. However, if you were to do that with a lock
> held that would instantly make lockdep report a deadlock, as the lock is
> then both used from IRQ context and has IRQs enabled.
> 
> So from a locking perspective you can assume no nesting, but from a
> state tracking pov we have to deal with the nesting I think (although it
> is very rare).

Got it. Thank you.

> You're asking this in relation to the rollback thing, right? I think we

Exactly. I wanted to make it clear when implementing the rollback for
irqs and works of workqueue.

> should only save the state when hardirq_context goes from 0->1 and
> restore on 1->0.

Yes, it's already done in v6, as you are saying.

Thank you very much.

RE: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

> -Original Message-
> From: Peter Zijlstra [mailto:pet...@infradead.org]
> Sent: Friday, May 19, 2017 7:30 PM
> To: Byungchul Park
> Cc: mi...@kernel.org; t...@linutronix.de; wal...@google.com;
> boqun.f...@gmail.com; kir...@shutemov.name; linux-kernel@vger.kernel.org;
> linux...@kvack.org; iamjoonsoo@lge.com; a...@linux-foundation.org;
> wi...@infradead.org; npig...@gmail.com; kernel-t...@lge.com
> Subject: Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature
> 
> On Fri, May 19, 2017 at 05:07:08PM +0900, Byungchul Park wrote:
> > On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > > Lockdep is a runtime locking correctness validator that detects and
> > > reports a deadlock or its possibility by checking dependencies between
> > > locks. It's useful since it does not report just an actual deadlock
> but
> > > also the possibility of a deadlock that has not actually happened yet.
> > > That enables problems to be fixed before they affect real systems.
> > >
> > > However, this facility is only applicable to typical locks, such as
> > > spinlocks and mutexes, which are normally released within the context
> in
> > > which they were acquired. However, synchronization primitives like
> page
> > > locks or completions, which are allowed to be released in any context,
> > > also create dependencies and can cause a deadlock. So lockdep should
> > > track these locks to do a better job. The 'crossrelease'
> implementation
> > > makes these primitives also be tracked.
> >
> > Excuse me but I have a question...
> >
> > Only for maskable irq, can I assume that hardirq are prevented within
> > hardirq context? I remember that nested interrupts were allowed in the
> > past but not recommanded. But what about now? I'm curious about the
> > overall direction of kernel and current status. It would be very
> > appriciated if you answer it.
> 
> So you're right. In general enabling IRQs from hardirq context is
> discouraged but allowed. However, if you were to do that with a lock
> held that would instantly make lockdep report a deadlock, as the lock is
> then both used from IRQ context and has IRQs enabled.
> 
> So from a locking perspective you can assume no nesting, but from a
> state tracking pov we have to deal with the nesting I think (although it
> is very rare).

Got it. Thank you.

> You're asking this in relation to the rollback thing, right? I think we

Exactly. I wanted to make it clear when implementing the rollback for
irqs and works of workqueue.

> should only save the state when hardirq_context goes from 0->1 and
> restore on 1->0.

Yes, it's already done in v6, as you are saying.

Thank you very much.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Fri, May 19, 2017 at 05:07:08PM +0900, Byungchul Park wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > Lockdep is a runtime locking correctness validator that detects and
> > reports a deadlock or its possibility by checking dependencies between
> > locks. It's useful since it does not report just an actual deadlock but
> > also the possibility of a deadlock that has not actually happened yet.
> > That enables problems to be fixed before they affect real systems.
> > 
> > However, this facility is only applicable to typical locks, such as
> > spinlocks and mutexes, which are normally released within the context in
> > which they were acquired. However, synchronization primitives like page
> > locks or completions, which are allowed to be released in any context,
> > also create dependencies and can cause a deadlock. So lockdep should
> > track these locks to do a better job. The 'crossrelease' implementation
> > makes these primitives also be tracked.
> 
> Excuse me but I have a question...
> 
> Only for maskable irq, can I assume that hardirq are prevented within
> hardirq context? I remember that nested interrupts were allowed in the
> past but not recommanded. But what about now? I'm curious about the
> overall direction of kernel and current status. It would be very
> appriciated if you answer it.

So you're right. In general enabling IRQs from hardirq context is
discouraged but allowed. However, if you were to do that with a lock
held that would instantly make lockdep report a deadlock, as the lock is
then both used from IRQ context and has IRQs enabled.

So from a locking perspective you can assume no nesting, but from a
state tracking pov we have to deal with the nesting I think (although it
is very rare).

You're asking this in relation to the rollback thing, right? I think we
should only save the state when hardirq_context goes from 0->1 and
restore on 1->0.

If you're asking this for another reason, please clarify.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Fri, May 19, 2017 at 05:07:08PM +0900, Byungchul Park wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > Lockdep is a runtime locking correctness validator that detects and
> > reports a deadlock or its possibility by checking dependencies between
> > locks. It's useful since it does not report just an actual deadlock but
> > also the possibility of a deadlock that has not actually happened yet.
> > That enables problems to be fixed before they affect real systems.
> > 
> > However, this facility is only applicable to typical locks, such as
> > spinlocks and mutexes, which are normally released within the context in
> > which they were acquired. However, synchronization primitives like page
> > locks or completions, which are allowed to be released in any context,
> > also create dependencies and can cause a deadlock. So lockdep should
> > track these locks to do a better job. The 'crossrelease' implementation
> > makes these primitives also be tracked.
> 
> Excuse me but I have a question...
> 
> Only for maskable irq, can I assume that hardirq are prevented within
> hardirq context? I remember that nested interrupts were allowed in the
> past but not recommanded. But what about now? I'm curious about the
> overall direction of kernel and current status. It would be very
> appriciated if you answer it.

So you're right. In general enabling IRQs from hardirq context is
discouraged but allowed. However, if you were to do that with a lock
held that would instantly make lockdep report a deadlock, as the lock is
then both used from IRQ context and has IRQs enabled.

So from a locking perspective you can assume no nesting, but from a
state tracking pov we have to deal with the nesting I think (although it
is very rare).

You're asking this in relation to the rollback thing, right? I think we
should only save the state when hardirq_context goes from 0->1 and
restore on 1->0.

If you're asking this for another reason, please clarify.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> Lockdep is a runtime locking correctness validator that detects and
> reports a deadlock or its possibility by checking dependencies between
> locks. It's useful since it does not report just an actual deadlock but
> also the possibility of a deadlock that has not actually happened yet.
> That enables problems to be fixed before they affect real systems.
> 
> However, this facility is only applicable to typical locks, such as
> spinlocks and mutexes, which are normally released within the context in
> which they were acquired. However, synchronization primitives like page
> locks or completions, which are allowed to be released in any context,
> also create dependencies and can cause a deadlock. So lockdep should
> track these locks to do a better job. The 'crossrelease' implementation
> makes these primitives also be tracked.

Excuse me but I have a question...

Only for maskable irq, can I assume that hardirq are prevented within
hardirq context? I remember that nested interrupts were allowed in the
past but not recommanded. But what about now? I'm curious about the
overall direction of kernel and current status. It would be very
appriciated if you answer it.

Thank you.
Byungchul

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> Lockdep is a runtime locking correctness validator that detects and
> reports a deadlock or its possibility by checking dependencies between
> locks. It's useful since it does not report just an actual deadlock but
> also the possibility of a deadlock that has not actually happened yet.
> That enables problems to be fixed before they affect real systems.
> 
> However, this facility is only applicable to typical locks, such as
> spinlocks and mutexes, which are normally released within the context in
> which they were acquired. However, synchronization primitives like page
> locks or completions, which are allowed to be released in any context,
> also create dependencies and can cause a deadlock. So lockdep should
> track these locks to do a better job. The 'crossrelease' implementation
> makes these primitives also be tracked.

Excuse me but I have a question...

Only for maskable irq, can I assume that hardirq are prevented within
hardirq context? I remember that nested interrupts were allowed in the
past but not recommanded. But what about now? I'm curious about the
overall direction of kernel and current status. It would be very
appriciated if you answer it.

Thank you.
Byungchul

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Tue, May 16, 2017 at 04:18:46PM +0200, Peter Zijlstra wrote:
> On Tue, Apr 25, 2017 at 02:40:44PM +0900, Byungchul Park wrote:
> > On Mon, Apr 24, 2017 at 12:17:47PM +0200, Peter Zijlstra wrote:
> 
> > > My complaint is mostly about naming.. and "hist_gen_id" might be a
> > > better name.
> > 
> > Ah, I also think the name, 'work_id', is not good... and frankly I am
> > not sure if 'hist_gen_id' is good, either. What about to apply 'rollback',
> > which I did for locks in irq, into works of workqueues? If you say yes,
> > I will try to do it.
> 
> If the rollback thing works, that's fine too. If it gets ugly, stick
> with something like 'hist_id'.

I really want to implement it with rollback.. But it also needs to
introduce new fields to distinguish between works which are all normal
process contexts.

I will do this with renaming instead of applying rollback.

Thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Tue, May 16, 2017 at 04:18:46PM +0200, Peter Zijlstra wrote:
> On Tue, Apr 25, 2017 at 02:40:44PM +0900, Byungchul Park wrote:
> > On Mon, Apr 24, 2017 at 12:17:47PM +0200, Peter Zijlstra wrote:
> 
> > > My complaint is mostly about naming.. and "hist_gen_id" might be a
> > > better name.
> > 
> > Ah, I also think the name, 'work_id', is not good... and frankly I am
> > not sure if 'hist_gen_id' is good, either. What about to apply 'rollback',
> > which I did for locks in irq, into works of workqueues? If you say yes,
> > I will try to do it.
> 
> If the rollback thing works, that's fine too. If it gets ugly, stick
> with something like 'hist_id'.

I really want to implement it with rollback.. But it also needs to
introduce new fields to distinguish between works which are all normal
process contexts.

I will do this with renaming instead of applying rollback.

Thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Apr 25, 2017 at 02:40:44PM +0900, Byungchul Park wrote:
> On Mon, Apr 24, 2017 at 12:17:47PM +0200, Peter Zijlstra wrote:

> > My complaint is mostly about naming.. and "hist_gen_id" might be a
> > better name.
> 
> Ah, I also think the name, 'work_id', is not good... and frankly I am
> not sure if 'hist_gen_id' is good, either. What about to apply 'rollback',
> which I did for locks in irq, into works of workqueues? If you say yes,
> I will try to do it.

If the rollback thing works, that's fine too. If it gets ugly, stick
with something like 'hist_id'.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Apr 25, 2017 at 02:40:44PM +0900, Byungchul Park wrote:
> On Mon, Apr 24, 2017 at 12:17:47PM +0200, Peter Zijlstra wrote:

> > My complaint is mostly about naming.. and "hist_gen_id" might be a
> > better name.
> 
> Ah, I also think the name, 'work_id', is not good... and frankly I am
> not sure if 'hist_gen_id' is good, either. What about to apply 'rollback',
> which I did for locks in irq, into works of workqueues? If you say yes,
> I will try to do it.

If the rollback thing works, that's fine too. If it gets ugly, stick
with something like 'hist_id'.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Mon, Apr 24, 2017 at 11:30:51AM +0200, Peter Zijlstra wrote:
> +static void add_xhlock(struct held_lock *hlock)
> +{
> +   unsigned int idx = current->xhlock_idx++;
> +   struct hist_lock *xhlock = (idx);
> 
> Yes, I misread that. Then '0' has the oldest entry, which is slightly
> weird. Should we change that?

I will just follow your decision. Do you think I should change it so
that 'xhlock_idx' points to newest one, or ok to keep it unchanged?

> 
> 
> > > > +
> > > > +   if (!xhlock_used(xhlock))
> > > > +   break;
> > > > +
> > > > +   if (before(xhlock->hlock.gen_id, xlock->hlock.gen_id))
> > > > +   break;
> > > > +
> > > > +   if (same_context_xhlock(xhlock) &&
> > > > +   !commit_xhlock(xlock, xhlock))
> > > 
> > > return with graph_lock held?
> > 
> > No. When commit_xhlock() returns 0, the lock was already unlocked.
> 
> Please add a comment, because I completely missed that. That's at least
> 2 functions deeper.

Yes, I will add a comment.

Thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Mon, Apr 24, 2017 at 11:30:51AM +0200, Peter Zijlstra wrote:
> +static void add_xhlock(struct held_lock *hlock)
> +{
> +   unsigned int idx = current->xhlock_idx++;
> +   struct hist_lock *xhlock = (idx);
> 
> Yes, I misread that. Then '0' has the oldest entry, which is slightly
> weird. Should we change that?

I will just follow your decision. Do you think I should change it so
that 'xhlock_idx' points to newest one, or ok to keep it unchanged?

> 
> 
> > > > +
> > > > +   if (!xhlock_used(xhlock))
> > > > +   break;
> > > > +
> > > > +   if (before(xhlock->hlock.gen_id, xlock->hlock.gen_id))
> > > > +   break;
> > > > +
> > > > +   if (same_context_xhlock(xhlock) &&
> > > > +   !commit_xhlock(xlock, xhlock))
> > > 
> > > return with graph_lock held?
> > 
> > No. When commit_xhlock() returns 0, the lock was already unlocked.
> 
> Please add a comment, because I completely missed that. That's at least
> 2 functions deeper.

Yes, I will add a comment.

Thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Mon, Apr 24, 2017 at 12:17:47PM +0200, Peter Zijlstra wrote:
> On Mon, Apr 24, 2017 at 02:11:02PM +0900, Byungchul Park wrote:
> > On Wed, Apr 19, 2017 at 04:25:03PM +0200, Peter Zijlstra wrote:
> 
> > > I still don't like work_id; it doesn't have anything to do with
> > > workqueues per se, other than the fact that they end up using it.
> > > 
> > > It's a history generation id; touching it completely invalidates our
> > > history. Workqueues need this because they run independent work from the
> > > same context.
> > > 
> > > But the same is true for other sites. Last time I suggested
> > > lockdep_assert_empty() to denote all suck places (and note we already
> > > have lockdep_sys_exit() that hooks into the return to user path).
> > 
> > I'm sorry but I don't understand what you intend. It would be appriciated
> > if you explain more.
> > 
> > You might know why I introduced the 'work_id'.. Is there any alternative?
> 
> My complaint is mostly about naming.. and "hist_gen_id" might be a
> better name.

Ah, I also think the name, 'work_id', is not good... and frankly I am
not sure if 'hist_gen_id' is good, either. What about to apply 'rollback',
which I did for locks in irq, into works of workqueues? If you say yes,
I will try to do it.

> But let me explain.
> 
> 
> The reason workqueues need this is because the lock history for each
> 'work' are independent. The locks of Work-B do not depend on the locks
> of the preceding Work-A, because the completion of Work-B is not
> dependent on those locks.
> 
> But this is true for many things; pretty much all kthreads fall in this
> pattern, where they have an 'idle' state and future completions do not
> depend on past completions. Its just that since they all have the 'same'
> form -- the kthread does the same over and over -- it doesn't matter
> much.
> 
> The same is true for system-calls, once a system call is complete (we've
> returned to userspace) the next system call does not depend on the lock
> history of the previous one.

Yes. I agree. As you said, actually two independent job e.g. syscalls,
works.. should not depend on each other.

Frankly speaking, nevertheless, if they depend on each other, then I
think it would be better to detect the cases, too. But for now, since
it's more important to avoid false positive detections, I will do it as
conservatively as possible, as my current implementation.

And thank you for additional explanation!

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Mon, Apr 24, 2017 at 12:17:47PM +0200, Peter Zijlstra wrote:
> On Mon, Apr 24, 2017 at 02:11:02PM +0900, Byungchul Park wrote:
> > On Wed, Apr 19, 2017 at 04:25:03PM +0200, Peter Zijlstra wrote:
> 
> > > I still don't like work_id; it doesn't have anything to do with
> > > workqueues per se, other than the fact that they end up using it.
> > > 
> > > It's a history generation id; touching it completely invalidates our
> > > history. Workqueues need this because they run independent work from the
> > > same context.
> > > 
> > > But the same is true for other sites. Last time I suggested
> > > lockdep_assert_empty() to denote all suck places (and note we already
> > > have lockdep_sys_exit() that hooks into the return to user path).
> > 
> > I'm sorry but I don't understand what you intend. It would be appriciated
> > if you explain more.
> > 
> > You might know why I introduced the 'work_id'.. Is there any alternative?
> 
> My complaint is mostly about naming.. and "hist_gen_id" might be a
> better name.

Ah, I also think the name, 'work_id', is not good... and frankly I am
not sure if 'hist_gen_id' is good, either. What about to apply 'rollback',
which I did for locks in irq, into works of workqueues? If you say yes,
I will try to do it.

> But let me explain.
> 
> 
> The reason workqueues need this is because the lock history for each
> 'work' are independent. The locks of Work-B do not depend on the locks
> of the preceding Work-A, because the completion of Work-B is not
> dependent on those locks.
> 
> But this is true for many things; pretty much all kthreads fall in this
> pattern, where they have an 'idle' state and future completions do not
> depend on past completions. Its just that since they all have the 'same'
> form -- the kthread does the same over and over -- it doesn't matter
> much.
> 
> The same is true for system-calls, once a system call is complete (we've
> returned to userspace) the next system call does not depend on the lock
> history of the previous one.

Yes. I agree. As you said, actually two independent job e.g. syscalls,
works.. should not depend on each other.

Frankly speaking, nevertheless, if they depend on each other, then I
think it would be better to detect the cases, too. But for now, since
it's more important to avoid false positive detections, I will do it as
conservatively as possible, as my current implementation.

And thank you for additional explanation!

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Mon, Apr 24, 2017 at 02:11:02PM +0900, Byungchul Park wrote:
> On Wed, Apr 19, 2017 at 04:25:03PM +0200, Peter Zijlstra wrote:

> > I still don't like work_id; it doesn't have anything to do with
> > workqueues per se, other than the fact that they end up using it.
> > 
> > It's a history generation id; touching it completely invalidates our
> > history. Workqueues need this because they run independent work from the
> > same context.
> > 
> > But the same is true for other sites. Last time I suggested
> > lockdep_assert_empty() to denote all suck places (and note we already
> > have lockdep_sys_exit() that hooks into the return to user path).
> 
> I'm sorry but I don't understand what you intend. It would be appriciated
> if you explain more.
> 
> You might know why I introduced the 'work_id'.. Is there any alternative?

My complaint is mostly about naming.. and "hist_gen_id" might be a
better name.

But let me explain.


The reason workqueues need this is because the lock history for each
'work' are independent. The locks of Work-B do not depend on the locks
of the preceding Work-A, because the completion of Work-B is not
dependent on those locks.

But this is true for many things; pretty much all kthreads fall in this
pattern, where they have an 'idle' state and future completions do not
depend on past completions. Its just that since they all have the 'same'
form -- the kthread does the same over and over -- it doesn't matter
much.

The same is true for system-calls, once a system call is complete (we've
returned to userspace) the next system call does not depend on the lock
history of the previous one.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Mon, Apr 24, 2017 at 02:11:02PM +0900, Byungchul Park wrote:
> On Wed, Apr 19, 2017 at 04:25:03PM +0200, Peter Zijlstra wrote:

> > I still don't like work_id; it doesn't have anything to do with
> > workqueues per se, other than the fact that they end up using it.
> > 
> > It's a history generation id; touching it completely invalidates our
> > history. Workqueues need this because they run independent work from the
> > same context.
> > 
> > But the same is true for other sites. Last time I suggested
> > lockdep_assert_empty() to denote all suck places (and note we already
> > have lockdep_sys_exit() that hooks into the return to user path).
> 
> I'm sorry but I don't understand what you intend. It would be appriciated
> if you explain more.
> 
> You might know why I introduced the 'work_id'.. Is there any alternative?

My complaint is mostly about naming.. and "hist_gen_id" might be a
better name.

But let me explain.


The reason workqueues need this is because the lock history for each
'work' are independent. The locks of Work-B do not depend on the locks
of the preceding Work-A, because the completion of Work-B is not
dependent on those locks.

But this is true for many things; pretty much all kthreads fall in this
pattern, where they have an 'idle' state and future completions do not
depend on past completions. Its just that since they all have the 'same'
form -- the kthread does the same over and over -- it doesn't matter
much.

The same is true for system-calls, once a system call is complete (we've
returned to userspace) the next system call does not depend on the lock
history of the previous one.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Mon, Apr 24, 2017 at 12:04:12PM +0900, Byungchul Park wrote:
> On Wed, Apr 19, 2017 at 07:19:54PM +0200, Peter Zijlstra wrote:
> > > +/*
> > > + * For crosslock.
> > > + */
> > > +static int add_xlock(struct held_lock *hlock)
> > > +{
> > > + struct cross_lock *xlock;
> > > + unsigned int gen_id;
> > > +
> > > + if (!graph_lock())
> > > + return 0;
> > > +
> > > + xlock = &((struct lockdep_map_cross *)hlock->instance)->xlock;
> > > +
> > > + gen_id = (unsigned int)atomic_inc_return(_gen_id);
> > > + xlock->hlock = *hlock;
> > > + xlock->hlock.gen_id = gen_id;
> > > + graph_unlock();
> > 
> > What does graph_lock protect here?
> 
> Modifying xlock(not xhlock) instance should be protected with graph_lock.
> Don't you think so?

Ah, right you are. I think I got confused between our xhlock (local)
array and the xlock instance thing. The latter needs protection to
serialize concurrent acquires.

> > > +static int commit_xhlocks(struct cross_lock *xlock)
> > > +{
> > > + unsigned int cur = current->xhlock_idx;
> > > + unsigned int i;
> > > +
> > > + if (!graph_lock())
> > > + return 0;
> > > +
> > > + for (i = cur - 1; !xhlock_same(i, cur); i--) {
> > > + struct hist_lock *xhlock = (i);
> > 
> > *blink*, you mean this?
> > 
> > for (i = 0; i < MAX_XHLOCKS_NR; i++) {
> > struct hist_lock *xhlock = (cur - i);
> 
> I will change the loop to this form.
> 
> > Except you seem to skip over the most recent element (@cur), why?
> 
> Currently 'cur' points to the next *free* slot.

Well, there's no such thing has a 'free' slot, its a _ring_ buffer.

But:

+static void add_xhlock(struct held_lock *hlock)
+{
+   unsigned int idx = current->xhlock_idx++;
+   struct hist_lock *xhlock = (idx);

Yes, I misread that. Then '0' has the oldest entry, which is slightly
weird. Should we change that?


> > > +
> > > + if (!xhlock_used(xhlock))
> > > + break;
> > > +
> > > + if (before(xhlock->hlock.gen_id, xlock->hlock.gen_id))
> > > + break;
> > > +
> > > + if (same_context_xhlock(xhlock) &&
> > > + !commit_xhlock(xlock, xhlock))
> > 
> > return with graph_lock held?
> 
> No. When commit_xhlock() returns 0, the lock was already unlocked.

Please add a comment, because I completely missed that. That's at least
2 functions deeper.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Mon, Apr 24, 2017 at 12:04:12PM +0900, Byungchul Park wrote:
> On Wed, Apr 19, 2017 at 07:19:54PM +0200, Peter Zijlstra wrote:
> > > +/*
> > > + * For crosslock.
> > > + */
> > > +static int add_xlock(struct held_lock *hlock)
> > > +{
> > > + struct cross_lock *xlock;
> > > + unsigned int gen_id;
> > > +
> > > + if (!graph_lock())
> > > + return 0;
> > > +
> > > + xlock = &((struct lockdep_map_cross *)hlock->instance)->xlock;
> > > +
> > > + gen_id = (unsigned int)atomic_inc_return(_gen_id);
> > > + xlock->hlock = *hlock;
> > > + xlock->hlock.gen_id = gen_id;
> > > + graph_unlock();
> > 
> > What does graph_lock protect here?
> 
> Modifying xlock(not xhlock) instance should be protected with graph_lock.
> Don't you think so?

Ah, right you are. I think I got confused between our xhlock (local)
array and the xlock instance thing. The latter needs protection to
serialize concurrent acquires.

> > > +static int commit_xhlocks(struct cross_lock *xlock)
> > > +{
> > > + unsigned int cur = current->xhlock_idx;
> > > + unsigned int i;
> > > +
> > > + if (!graph_lock())
> > > + return 0;
> > > +
> > > + for (i = cur - 1; !xhlock_same(i, cur); i--) {
> > > + struct hist_lock *xhlock = (i);
> > 
> > *blink*, you mean this?
> > 
> > for (i = 0; i < MAX_XHLOCKS_NR; i++) {
> > struct hist_lock *xhlock = (cur - i);
> 
> I will change the loop to this form.
> 
> > Except you seem to skip over the most recent element (@cur), why?
> 
> Currently 'cur' points to the next *free* slot.

Well, there's no such thing has a 'free' slot, its a _ring_ buffer.

But:

+static void add_xhlock(struct held_lock *hlock)
+{
+   unsigned int idx = current->xhlock_idx++;
+   struct hist_lock *xhlock = (idx);

Yes, I misread that. Then '0' has the oldest entry, which is slightly
weird. Should we change that?


> > > +
> > > + if (!xhlock_used(xhlock))
> > > + break;
> > > +
> > > + if (before(xhlock->hlock.gen_id, xlock->hlock.gen_id))
> > > + break;
> > > +
> > > + if (same_context_xhlock(xhlock) &&
> > > + !commit_xhlock(xlock, xhlock))
> > 
> > return with graph_lock held?
> 
> No. When commit_xhlock() returns 0, the lock was already unlocked.

Please add a comment, because I completely missed that. That's at least
2 functions deeper.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 04:25:03PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +struct hist_lock {
> > +   /*
> > +* Each work of workqueue might run in a different context,
> > +* thanks to concurrency support of workqueue. So we have to
> > +* distinguish each work to avoid false positive.
> > +*/
> > +   unsigned intwork_id;
> >  };
> 
> > @@ -1749,6 +1749,14 @@ struct task_struct {
> > struct held_lock held_locks[MAX_LOCK_DEPTH];
> > gfp_t lockdep_reclaim_gfp;
> >  #endif
> > +#ifdef CONFIG_LOCKDEP_CROSSRELEASE
> > +#define MAX_XHLOCKS_NR 64UL
> > +   struct hist_lock *xhlocks; /* Crossrelease history locks */
> > +   unsigned int xhlock_idx;
> > +   unsigned int xhlock_idx_soft; /* For backing up at softirq entry */
> > +   unsigned int xhlock_idx_hard; /* For backing up at hardirq entry */
> > +   unsigned int work_id;
> > +#endif
> >  #ifdef CONFIG_UBSAN
> > unsigned int in_ubsan;
> >  #endif
> 
> > +/*
> > + * Crossrelease needs to distinguish each work of workqueues.
> > + * Caller is supposed to be a worker.
> > + */
> > +void crossrelease_work_start(void)
> > +{
> > +   if (current->xhlocks)
> > +   current->work_id++;
> > +}
> 
> > +/*
> > + * Only access local task's data, so irq disable is only required.
> > + */
> > +static int same_context_xhlock(struct hist_lock *xhlock)
> > +{
> > +   struct task_struct *curr = current;
> > +
> > +   /* In the case of hardirq context */
> > +   if (curr->hardirq_context) {
> > +   if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> > +   return 1;
> > +   /* In the case of softriq context */
> > +   } else if (curr->softirq_context) {
> > +   if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> > +   return 1;
> > +   /* In the case of process context */
> > +   } else {
> > +   if (xhlock->work_id == curr->work_id)
> > +   return 1;
> > +   }
> > +   return 0;
> > +}
> 
> I still don't like work_id; it doesn't have anything to do with
> workqueues per se, other than the fact that they end up using it.
> 
> It's a history generation id; touching it completely invalidates our
> history. Workqueues need this because they run independent work from the
> same context.
> 
> But the same is true for other sites. Last time I suggested
> lockdep_assert_empty() to denote all suck places (and note we already
> have lockdep_sys_exit() that hooks into the return to user path).

I'm sorry but I don't understand what you intend. It would be appriciated
if you explain more.

You might know why I introduced the 'work_id'.. Is there any alternative?

Thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 04:25:03PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +struct hist_lock {
> > +   /*
> > +* Each work of workqueue might run in a different context,
> > +* thanks to concurrency support of workqueue. So we have to
> > +* distinguish each work to avoid false positive.
> > +*/
> > +   unsigned intwork_id;
> >  };
> 
> > @@ -1749,6 +1749,14 @@ struct task_struct {
> > struct held_lock held_locks[MAX_LOCK_DEPTH];
> > gfp_t lockdep_reclaim_gfp;
> >  #endif
> > +#ifdef CONFIG_LOCKDEP_CROSSRELEASE
> > +#define MAX_XHLOCKS_NR 64UL
> > +   struct hist_lock *xhlocks; /* Crossrelease history locks */
> > +   unsigned int xhlock_idx;
> > +   unsigned int xhlock_idx_soft; /* For backing up at softirq entry */
> > +   unsigned int xhlock_idx_hard; /* For backing up at hardirq entry */
> > +   unsigned int work_id;
> > +#endif
> >  #ifdef CONFIG_UBSAN
> > unsigned int in_ubsan;
> >  #endif
> 
> > +/*
> > + * Crossrelease needs to distinguish each work of workqueues.
> > + * Caller is supposed to be a worker.
> > + */
> > +void crossrelease_work_start(void)
> > +{
> > +   if (current->xhlocks)
> > +   current->work_id++;
> > +}
> 
> > +/*
> > + * Only access local task's data, so irq disable is only required.
> > + */
> > +static int same_context_xhlock(struct hist_lock *xhlock)
> > +{
> > +   struct task_struct *curr = current;
> > +
> > +   /* In the case of hardirq context */
> > +   if (curr->hardirq_context) {
> > +   if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> > +   return 1;
> > +   /* In the case of softriq context */
> > +   } else if (curr->softirq_context) {
> > +   if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> > +   return 1;
> > +   /* In the case of process context */
> > +   } else {
> > +   if (xhlock->work_id == curr->work_id)
> > +   return 1;
> > +   }
> > +   return 0;
> > +}
> 
> I still don't like work_id; it doesn't have anything to do with
> workqueues per se, other than the fact that they end up using it.
> 
> It's a history generation id; touching it completely invalidates our
> history. Workqueues need this because they run independent work from the
> same context.
> 
> But the same is true for other sites. Last time I suggested
> lockdep_assert_empty() to denote all suck places (and note we already
> have lockdep_sys_exit() that hooks into the return to user path).

I'm sorry but I don't understand what you intend. It would be appriciated
if you explain more.

You might know why I introduced the 'work_id'.. Is there any alternative?

Thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 05:08:35PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +/*
> > + * Only access local task's data, so irq disable is only required.
> > + */
> > +static int same_context_xhlock(struct hist_lock *xhlock)
> > +{
> > +   struct task_struct *curr = current;
> > +
> > +   /* In the case of hardirq context */
> > +   if (curr->hardirq_context) {
> > +   if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> > +   return 1;
> > +   /* In the case of softriq context */
> > +   } else if (curr->softirq_context) {
> > +   if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> > +   return 1;
> > +   /* In the case of process context */
> > +   } else {
> > +   if (xhlock->work_id == curr->work_id)
> > +   return 1;
> > +   }
> > +   return 0;
> > +}
> 
> static bool same_context_xhlock(struct hist_lock *xhlock)
> {
>   return xhlock->hlock.irq_context == task_irq_context(current) &&
>  xhlock->work_id == current->work_id;
> }

D'oh, thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 05:08:35PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +/*
> > + * Only access local task's data, so irq disable is only required.
> > + */
> > +static int same_context_xhlock(struct hist_lock *xhlock)
> > +{
> > +   struct task_struct *curr = current;
> > +
> > +   /* In the case of hardirq context */
> > +   if (curr->hardirq_context) {
> > +   if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> > +   return 1;
> > +   /* In the case of softriq context */
> > +   } else if (curr->softirq_context) {
> > +   if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> > +   return 1;
> > +   /* In the case of process context */
> > +   } else {
> > +   if (xhlock->work_id == curr->work_id)
> > +   return 1;
> > +   }
> > +   return 0;
> > +}
> 
> static bool same_context_xhlock(struct hist_lock *xhlock)
> {
>   return xhlock->hlock.irq_context == task_irq_context(current) &&
>  xhlock->work_id == current->work_id;
> }

D'oh, thank you.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 07:20:19PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +config LOCKDEP_CROSSRELEASE
> > +   bool "Lock debugging: make lockdep work for crosslocks"
> > +   select PROVE_LOCKING
> 
>   depends PROVE_LOCKING
> 
> instead ?

OK. I will change it.

> 
> > +   default n
> > +   help
> > +This makes lockdep work for crosslock which is a lock allowed to
> > +be released in a different context from the acquisition context.
> > +Normally a lock must be released in the context acquiring the lock.
> > +However, relexing this constraint helps synchronization primitives
> > +such as page locks or completions can use the lock correctness
> > +detector, lockdep.
> > +
> >  config PROVE_LOCKING
> > bool "Lock debugging: prove locking correctness"
> > depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT 
> > && LOCKDEP_SUPPORT
> > -- 
> > 1.9.1
> > 

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 07:20:19PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +config LOCKDEP_CROSSRELEASE
> > +   bool "Lock debugging: make lockdep work for crosslocks"
> > +   select PROVE_LOCKING
> 
>   depends PROVE_LOCKING
> 
> instead ?

OK. I will change it.

> 
> > +   default n
> > +   help
> > +This makes lockdep work for crosslock which is a lock allowed to
> > +be released in a different context from the acquisition context.
> > +Normally a lock must be released in the context acquiring the lock.
> > +However, relexing this constraint helps synchronization primitives
> > +such as page locks or completions can use the lock correctness
> > +detector, lockdep.
> > +
> >  config PROVE_LOCKING
> > bool "Lock debugging: prove locking correctness"
> > depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT 
> > && LOCKDEP_SUPPORT
> > -- 
> > 1.9.1
> > 

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 07:19:54PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +/*
> > + * Only access local task's data, so irq disable is only required.
> 
> A comment describing what it does; record a hist_lock entry; would be
> more useful.

Right. I will add it.

> > + */
> > +static void add_xhlock(struct held_lock *hlock)
> > +{
> > +   unsigned int idx = current->xhlock_idx++;
> > +   struct hist_lock *xhlock = (idx);
> > +
> > +   /* Initialize hist_lock's members */
> > +   xhlock->hlock = *hlock;
> > +   xhlock->work_id = current->work_id;
> > +
> > +   xhlock->trace.nr_entries = 0;
> > +   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > +   xhlock->trace.entries = xhlock->trace_entries;
> > +   xhlock->trace.skip = 3;
> > +   save_stack_trace(>trace);
> > +}
> 
> > +/*
> > + * This should be lockless as far as possible because this would be
> > + * called very frequently.
> 
> idem; explain why depend_before().

Right. I will add a comment on the following 'if' statement.

> > + */
> > +static void check_add_xhlock(struct held_lock *hlock)
> > +{
> 
> The other thing could be done like:
> 
> #ifdef CONFIG_DEBUG_LOCKDEP
>   /*
>* This can be done locklessly because its all task-local state,
>* we must however ensure IRQs are disabled.
>*/
>   WARN_ON_ONCE(!irqs_disabled());
> #endif

Yes. Much better.

> > +   if (!current->xhlocks || !depend_before(hlock))
> > +   return;
> > +
> > +   add_xhlock(hlock);
> > +}
> 
> 
> > +
> > +/*
> > + * For crosslock.
> > + */
> > +static int add_xlock(struct held_lock *hlock)
> > +{
> > +   struct cross_lock *xlock;
> > +   unsigned int gen_id;
> > +
> > +   if (!graph_lock())
> > +   return 0;
> > +
> > +   xlock = &((struct lockdep_map_cross *)hlock->instance)->xlock;
> > +
> > +   gen_id = (unsigned int)atomic_inc_return(_gen_id);
> > +   xlock->hlock = *hlock;
> > +   xlock->hlock.gen_id = gen_id;
> > +   graph_unlock();
> 
> What does graph_lock protect here?

Modifying xlock(not xhlock) instance should be protected with graph_lock.
Don't you think so?

> > +
> > +   return 1;
> > +}
> > +
> > +/*
> > + * return 0: Stop. Failed to acquire graph_lock.
> > + * return 1: Done. No more acquire ops is needed.
> > + * return 2: Need to do normal acquire operation.
> > + */
> > +static int lock_acquire_crosslock(struct held_lock *hlock)
> > +{
> > +   /*
> > +*  CONTEXT 1   CONTEXT 2
> > +*  -   -
> > +*  lock A (cross)
> > +*  X = atomic_inc_return(_gen_id)
> > +*  ~
> > +*  Y = atomic_read_acquire(_gen_id)
> > +*  lock B
> > +*
> > +* atomic_read_acquire() is for ordering between A and B,
> > +* IOW, A happens before B, when CONTEXT 2 see Y >= X.
> > +*
> > +* Pairs with atomic_inc_return() in add_xlock().
> > +*/
> > +   hlock->gen_id = (unsigned int)atomic_read_acquire(_gen_id);
> > +
> > +   if (cross_lock(hlock->instance))
> > +   return add_xlock(hlock);
> > +
> > +   check_add_xhlock(hlock);
> > +   return 2;
> > +}
> 
> So I was wondering WTH we'd call into this with a !xlock to begin with.
> 
> Maybe something like:
> 
> /*
>  * Called for both normal and crosslock acquires. Normal locks will be
>  * pushed on the hist_lock queue. Cross locks will record state and
>  * stop regular lock_acquire() to avoid being placed on the held_lock
>  * stack.
>  *
>  * Returns: 0 - failure;
>  *  1 - cross-lock, done;
>  *  2 - normal lock, continue to held_lock[].
>  */

Why not? I will replace my comment with yours.

> > +static int commit_xhlock(struct cross_lock *xlock, struct hist_lock 
> > *xhlock)
> > +{
> > +   unsigned int xid, pid;
> > +   u64 chain_key;
> > +
> > +   xid = xlock_class(xlock) - lock_classes;
> > +   chain_key = iterate_chain_key((u64)0, xid);
> > +   pid = xhlock_class(xhlock) - lock_classes;
> > +   chain_key = iterate_chain_key(chain_key, pid);
> > +
> > +   if (lookup_chain_cache(chain_key))
> > +   return 1;
> > +
> > +   if (!add_chain_cache_classes(xid, pid, xhlock->hlock.irq_context,
> > +   chain_key))
> > +   return 0;
> > +
> > +   if (!check_prev_add(current, >hlock, >hlock, 1,
> > +   >trace, copy_trace))
> > +   return 0;
> > +
> > +   return 1;
> > +}
> > +
> > +static int commit_xhlocks(struct cross_lock *xlock)
> > +{
> > +   unsigned int cur = current->xhlock_idx;
> > +   unsigned int i;
> > +
> > +   if (!graph_lock())
> > +   return 0;
> > +
> > +   for (i = cur - 1; !xhlock_same(i, cur); i--) {
> > +   struct hist_lock *xhlock = (i);
> 
> *blink*, you mean this?
> 
>   for (i = 0; i < MAX_XHLOCKS_NR; i++) {
>   struct hist_lock *xhlock = (cur - i);

I will change the loop to this form.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

On Wed, Apr 19, 2017 at 07:19:54PM +0200, Peter Zijlstra wrote:
> On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> > +/*
> > + * Only access local task's data, so irq disable is only required.
> 
> A comment describing what it does; record a hist_lock entry; would be
> more useful.

Right. I will add it.

> > + */
> > +static void add_xhlock(struct held_lock *hlock)
> > +{
> > +   unsigned int idx = current->xhlock_idx++;
> > +   struct hist_lock *xhlock = (idx);
> > +
> > +   /* Initialize hist_lock's members */
> > +   xhlock->hlock = *hlock;
> > +   xhlock->work_id = current->work_id;
> > +
> > +   xhlock->trace.nr_entries = 0;
> > +   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > +   xhlock->trace.entries = xhlock->trace_entries;
> > +   xhlock->trace.skip = 3;
> > +   save_stack_trace(>trace);
> > +}
> 
> > +/*
> > + * This should be lockless as far as possible because this would be
> > + * called very frequently.
> 
> idem; explain why depend_before().

Right. I will add a comment on the following 'if' statement.

> > + */
> > +static void check_add_xhlock(struct held_lock *hlock)
> > +{
> 
> The other thing could be done like:
> 
> #ifdef CONFIG_DEBUG_LOCKDEP
>   /*
>* This can be done locklessly because its all task-local state,
>* we must however ensure IRQs are disabled.
>*/
>   WARN_ON_ONCE(!irqs_disabled());
> #endif

Yes. Much better.

> > +   if (!current->xhlocks || !depend_before(hlock))
> > +   return;
> > +
> > +   add_xhlock(hlock);
> > +}
> 
> 
> > +
> > +/*
> > + * For crosslock.
> > + */
> > +static int add_xlock(struct held_lock *hlock)
> > +{
> > +   struct cross_lock *xlock;
> > +   unsigned int gen_id;
> > +
> > +   if (!graph_lock())
> > +   return 0;
> > +
> > +   xlock = &((struct lockdep_map_cross *)hlock->instance)->xlock;
> > +
> > +   gen_id = (unsigned int)atomic_inc_return(_gen_id);
> > +   xlock->hlock = *hlock;
> > +   xlock->hlock.gen_id = gen_id;
> > +   graph_unlock();
> 
> What does graph_lock protect here?

Modifying xlock(not xhlock) instance should be protected with graph_lock.
Don't you think so?

> > +
> > +   return 1;
> > +}
> > +
> > +/*
> > + * return 0: Stop. Failed to acquire graph_lock.
> > + * return 1: Done. No more acquire ops is needed.
> > + * return 2: Need to do normal acquire operation.
> > + */
> > +static int lock_acquire_crosslock(struct held_lock *hlock)
> > +{
> > +   /*
> > +*  CONTEXT 1   CONTEXT 2
> > +*  -   -
> > +*  lock A (cross)
> > +*  X = atomic_inc_return(_gen_id)
> > +*  ~
> > +*  Y = atomic_read_acquire(_gen_id)
> > +*  lock B
> > +*
> > +* atomic_read_acquire() is for ordering between A and B,
> > +* IOW, A happens before B, when CONTEXT 2 see Y >= X.
> > +*
> > +* Pairs with atomic_inc_return() in add_xlock().
> > +*/
> > +   hlock->gen_id = (unsigned int)atomic_read_acquire(_gen_id);
> > +
> > +   if (cross_lock(hlock->instance))
> > +   return add_xlock(hlock);
> > +
> > +   check_add_xhlock(hlock);
> > +   return 2;
> > +}
> 
> So I was wondering WTH we'd call into this with a !xlock to begin with.
> 
> Maybe something like:
> 
> /*
>  * Called for both normal and crosslock acquires. Normal locks will be
>  * pushed on the hist_lock queue. Cross locks will record state and
>  * stop regular lock_acquire() to avoid being placed on the held_lock
>  * stack.
>  *
>  * Returns: 0 - failure;
>  *  1 - cross-lock, done;
>  *  2 - normal lock, continue to held_lock[].
>  */

Why not? I will replace my comment with yours.

> > +static int commit_xhlock(struct cross_lock *xlock, struct hist_lock 
> > *xhlock)
> > +{
> > +   unsigned int xid, pid;
> > +   u64 chain_key;
> > +
> > +   xid = xlock_class(xlock) - lock_classes;
> > +   chain_key = iterate_chain_key((u64)0, xid);
> > +   pid = xhlock_class(xhlock) - lock_classes;
> > +   chain_key = iterate_chain_key(chain_key, pid);
> > +
> > +   if (lookup_chain_cache(chain_key))
> > +   return 1;
> > +
> > +   if (!add_chain_cache_classes(xid, pid, xhlock->hlock.irq_context,
> > +   chain_key))
> > +   return 0;
> > +
> > +   if (!check_prev_add(current, >hlock, >hlock, 1,
> > +   >trace, copy_trace))
> > +   return 0;
> > +
> > +   return 1;
> > +}
> > +
> > +static int commit_xhlocks(struct cross_lock *xlock)
> > +{
> > +   unsigned int cur = current->xhlock_idx;
> > +   unsigned int i;
> > +
> > +   if (!graph_lock())
> > +   return 0;
> > +
> > +   for (i = cur - 1; !xhlock_same(i, cur); i--) {
> > +   struct hist_lock *xhlock = (i);
> 
> *blink*, you mean this?
> 
>   for (i = 0; i < MAX_XHLOCKS_NR; i++) {
>   struct hist_lock *xhlock = (cur - i);

I will change the loop to this form.

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +config LOCKDEP_CROSSRELEASE
> + bool "Lock debugging: make lockdep work for crosslocks"
> + select PROVE_LOCKING

depends PROVE_LOCKING

instead ?

> + default n
> + help
> +  This makes lockdep work for crosslock which is a lock allowed to
> +  be released in a different context from the acquisition context.
> +  Normally a lock must be released in the context acquiring the lock.
> +  However, relexing this constraint helps synchronization primitives
> +  such as page locks or completions can use the lock correctness
> +  detector, lockdep.
> +
>  config PROVE_LOCKING
>   bool "Lock debugging: prove locking correctness"
>   depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT 
> && LOCKDEP_SUPPORT
> -- 
> 1.9.1
> 

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +config LOCKDEP_CROSSRELEASE
> + bool "Lock debugging: make lockdep work for crosslocks"
> + select PROVE_LOCKING

depends PROVE_LOCKING

instead ?

> + default n
> + help
> +  This makes lockdep work for crosslock which is a lock allowed to
> +  be released in a different context from the acquisition context.
> +  Normally a lock must be released in the context acquiring the lock.
> +  However, relexing this constraint helps synchronization primitives
> +  such as page locks or completions can use the lock correctness
> +  detector, lockdep.
> +
>  config PROVE_LOCKING
>   bool "Lock debugging: prove locking correctness"
>   depends on DEBUG_KERNEL && TRACE_IRQFLAGS_SUPPORT && STACKTRACE_SUPPORT 
> && LOCKDEP_SUPPORT
> -- 
> 1.9.1
> 

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +/*
> + * Only access local task's data, so irq disable is only required.

A comment describing what it does; record a hist_lock entry; would be
more useful.

> + */
> +static void add_xhlock(struct held_lock *hlock)
> +{
> + unsigned int idx = current->xhlock_idx++;
> + struct hist_lock *xhlock = (idx);
> +
> + /* Initialize hist_lock's members */
> + xhlock->hlock = *hlock;
> + xhlock->work_id = current->work_id;
> +
> + xhlock->trace.nr_entries = 0;
> + xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> + xhlock->trace.entries = xhlock->trace_entries;
> + xhlock->trace.skip = 3;
> + save_stack_trace(>trace);
> +}

> +/*
> + * This should be lockless as far as possible because this would be
> + * called very frequently.

idem; explain why depend_before().

> + */
> +static void check_add_xhlock(struct held_lock *hlock)
> +{

The other thing could be done like:

#ifdef CONFIG_DEBUG_LOCKDEP
/*
 * This can be done locklessly because its all task-local state,
 * we must however ensure IRQs are disabled.
 */
WARN_ON_ONCE(!irqs_disabled());
#endif

> + if (!current->xhlocks || !depend_before(hlock))
> + return;
> +
> + add_xhlock(hlock);
> +}


> +
> +/*
> + * For crosslock.
> + */
> +static int add_xlock(struct held_lock *hlock)
> +{
> + struct cross_lock *xlock;
> + unsigned int gen_id;
> +
> + if (!graph_lock())
> + return 0;
> +
> + xlock = &((struct lockdep_map_cross *)hlock->instance)->xlock;
> +
> + gen_id = (unsigned int)atomic_inc_return(_gen_id);
> + xlock->hlock = *hlock;
> + xlock->hlock.gen_id = gen_id;
> + graph_unlock();

What does graph_lock protect here?

> +
> + return 1;
> +}
> +
> +/*
> + * return 0: Stop. Failed to acquire graph_lock.
> + * return 1: Done. No more acquire ops is needed.
> + * return 2: Need to do normal acquire operation.
> + */
> +static int lock_acquire_crosslock(struct held_lock *hlock)
> +{
> + /*
> +  *  CONTEXT 1   CONTEXT 2
> +  *  -   -
> +  *  lock A (cross)
> +  *  X = atomic_inc_return(_gen_id)
> +  *  ~
> +  *  Y = atomic_read_acquire(_gen_id)
> +  *  lock B
> +  *
> +  * atomic_read_acquire() is for ordering between A and B,
> +  * IOW, A happens before B, when CONTEXT 2 see Y >= X.
> +  *
> +  * Pairs with atomic_inc_return() in add_xlock().
> +  */
> + hlock->gen_id = (unsigned int)atomic_read_acquire(_gen_id);
> +
> + if (cross_lock(hlock->instance))
> + return add_xlock(hlock);
> +
> + check_add_xhlock(hlock);
> + return 2;
> +}

So I was wondering WTH we'd call into this with a !xlock to begin with.

Maybe something like:

/*
 * Called for both normal and crosslock acquires. Normal locks will be
 * pushed on the hist_lock queue. Cross locks will record state and
 * stop regular lock_acquire() to avoid being placed on the held_lock
 * stack.
 *
 * Returns: 0 - failure;
 *  1 - cross-lock, done;
 *  2 - normal lock, continue to held_lock[].
 */


> +static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
> +{
> + unsigned int xid, pid;
> + u64 chain_key;
> +
> + xid = xlock_class(xlock) - lock_classes;
> + chain_key = iterate_chain_key((u64)0, xid);
> + pid = xhlock_class(xhlock) - lock_classes;
> + chain_key = iterate_chain_key(chain_key, pid);
> +
> + if (lookup_chain_cache(chain_key))
> + return 1;
> +
> + if (!add_chain_cache_classes(xid, pid, xhlock->hlock.irq_context,
> + chain_key))
> + return 0;
> +
> + if (!check_prev_add(current, >hlock, >hlock, 1,
> + >trace, copy_trace))
> + return 0;
> +
> + return 1;
> +}
> +
> +static int commit_xhlocks(struct cross_lock *xlock)
> +{
> + unsigned int cur = current->xhlock_idx;
> + unsigned int i;
> +
> + if (!graph_lock())
> + return 0;
> +
> + for (i = cur - 1; !xhlock_same(i, cur); i--) {
> + struct hist_lock *xhlock = (i);

*blink*, you mean this?

for (i = 0; i < MAX_XHLOCKS_NR; i++) {
struct hist_lock *xhlock = (cur - i);

Except you seem to skip over the most recent element (@cur), why?

> +
> + if (!xhlock_used(xhlock))
> + break;
> +
> + if (before(xhlock->hlock.gen_id, xlock->hlock.gen_id))
> + break;
> +
> + if (same_context_xhlock(xhlock) &&
> + !commit_xhlock(xlock, xhlock))

return with graph_lock held?

> + return 0;
> + }
> +
> + graph_unlock();
> + return 1;
> +}
> +
> +void lock_commit_crosslock(struct 

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +/*
> + * Only access local task's data, so irq disable is only required.

A comment describing what it does; record a hist_lock entry; would be
more useful.

> + */
> +static void add_xhlock(struct held_lock *hlock)
> +{
> + unsigned int idx = current->xhlock_idx++;
> + struct hist_lock *xhlock = (idx);
> +
> + /* Initialize hist_lock's members */
> + xhlock->hlock = *hlock;
> + xhlock->work_id = current->work_id;
> +
> + xhlock->trace.nr_entries = 0;
> + xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> + xhlock->trace.entries = xhlock->trace_entries;
> + xhlock->trace.skip = 3;
> + save_stack_trace(>trace);
> +}

> +/*
> + * This should be lockless as far as possible because this would be
> + * called very frequently.

idem; explain why depend_before().

> + */
> +static void check_add_xhlock(struct held_lock *hlock)
> +{

The other thing could be done like:

#ifdef CONFIG_DEBUG_LOCKDEP
/*
 * This can be done locklessly because its all task-local state,
 * we must however ensure IRQs are disabled.
 */
WARN_ON_ONCE(!irqs_disabled());
#endif

> + if (!current->xhlocks || !depend_before(hlock))
> + return;
> +
> + add_xhlock(hlock);
> +}


> +
> +/*
> + * For crosslock.
> + */
> +static int add_xlock(struct held_lock *hlock)
> +{
> + struct cross_lock *xlock;
> + unsigned int gen_id;
> +
> + if (!graph_lock())
> + return 0;
> +
> + xlock = &((struct lockdep_map_cross *)hlock->instance)->xlock;
> +
> + gen_id = (unsigned int)atomic_inc_return(_gen_id);
> + xlock->hlock = *hlock;
> + xlock->hlock.gen_id = gen_id;
> + graph_unlock();

What does graph_lock protect here?

> +
> + return 1;
> +}
> +
> +/*
> + * return 0: Stop. Failed to acquire graph_lock.
> + * return 1: Done. No more acquire ops is needed.
> + * return 2: Need to do normal acquire operation.
> + */
> +static int lock_acquire_crosslock(struct held_lock *hlock)
> +{
> + /*
> +  *  CONTEXT 1   CONTEXT 2
> +  *  -   -
> +  *  lock A (cross)
> +  *  X = atomic_inc_return(_gen_id)
> +  *  ~
> +  *  Y = atomic_read_acquire(_gen_id)
> +  *  lock B
> +  *
> +  * atomic_read_acquire() is for ordering between A and B,
> +  * IOW, A happens before B, when CONTEXT 2 see Y >= X.
> +  *
> +  * Pairs with atomic_inc_return() in add_xlock().
> +  */
> + hlock->gen_id = (unsigned int)atomic_read_acquire(_gen_id);
> +
> + if (cross_lock(hlock->instance))
> + return add_xlock(hlock);
> +
> + check_add_xhlock(hlock);
> + return 2;
> +}

So I was wondering WTH we'd call into this with a !xlock to begin with.

Maybe something like:

/*
 * Called for both normal and crosslock acquires. Normal locks will be
 * pushed on the hist_lock queue. Cross locks will record state and
 * stop regular lock_acquire() to avoid being placed on the held_lock
 * stack.
 *
 * Returns: 0 - failure;
 *  1 - cross-lock, done;
 *  2 - normal lock, continue to held_lock[].
 */


> +static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
> +{
> + unsigned int xid, pid;
> + u64 chain_key;
> +
> + xid = xlock_class(xlock) - lock_classes;
> + chain_key = iterate_chain_key((u64)0, xid);
> + pid = xhlock_class(xhlock) - lock_classes;
> + chain_key = iterate_chain_key(chain_key, pid);
> +
> + if (lookup_chain_cache(chain_key))
> + return 1;
> +
> + if (!add_chain_cache_classes(xid, pid, xhlock->hlock.irq_context,
> + chain_key))
> + return 0;
> +
> + if (!check_prev_add(current, >hlock, >hlock, 1,
> + >trace, copy_trace))
> + return 0;
> +
> + return 1;
> +}
> +
> +static int commit_xhlocks(struct cross_lock *xlock)
> +{
> + unsigned int cur = current->xhlock_idx;
> + unsigned int i;
> +
> + if (!graph_lock())
> + return 0;
> +
> + for (i = cur - 1; !xhlock_same(i, cur); i--) {
> + struct hist_lock *xhlock = (i);

*blink*, you mean this?

for (i = 0; i < MAX_XHLOCKS_NR; i++) {
struct hist_lock *xhlock = (cur - i);

Except you seem to skip over the most recent element (@cur), why?

> +
> + if (!xhlock_used(xhlock))
> + break;
> +
> + if (before(xhlock->hlock.gen_id, xlock->hlock.gen_id))
> + break;
> +
> + if (same_context_xhlock(xhlock) &&
> + !commit_xhlock(xlock, xhlock))

return with graph_lock held?

> + return 0;
> + }
> +
> + graph_unlock();
> + return 1;
> +}
> +
> +void lock_commit_crosslock(struct 

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +/*
> + * Only access local task's data, so irq disable is only required.
> + */
> +static int same_context_xhlock(struct hist_lock *xhlock)
> +{
> + struct task_struct *curr = current;
> +
> + /* In the case of hardirq context */
> + if (curr->hardirq_context) {
> + if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> + return 1;
> + /* In the case of softriq context */
> + } else if (curr->softirq_context) {
> + if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> + return 1;
> + /* In the case of process context */
> + } else {
> + if (xhlock->work_id == curr->work_id)
> + return 1;
> + }
> + return 0;
> +}

static bool same_context_xhlock(struct hist_lock *xhlock)
{
return xhlock->hlock.irq_context == task_irq_context(current) &&
   xhlock->work_id == current->work_id;
}

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +/*
> + * Only access local task's data, so irq disable is only required.
> + */
> +static int same_context_xhlock(struct hist_lock *xhlock)
> +{
> + struct task_struct *curr = current;
> +
> + /* In the case of hardirq context */
> + if (curr->hardirq_context) {
> + if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> + return 1;
> + /* In the case of softriq context */
> + } else if (curr->softirq_context) {
> + if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> + return 1;
> + /* In the case of process context */
> + } else {
> + if (xhlock->work_id == curr->work_id)
> + return 1;
> + }
> + return 0;
> +}

static bool same_context_xhlock(struct hist_lock *xhlock)
{
return xhlock->hlock.irq_context == task_irq_context(current) &&
   xhlock->work_id == current->work_id;
}

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +struct hist_lock {
> + /*
> +  * Each work of workqueue might run in a different context,
> +  * thanks to concurrency support of workqueue. So we have to
> +  * distinguish each work to avoid false positive.
> +  */
> + unsigned intwork_id;
>  };

> @@ -1749,6 +1749,14 @@ struct task_struct {
>   struct held_lock held_locks[MAX_LOCK_DEPTH];
>   gfp_t lockdep_reclaim_gfp;
>  #endif
> +#ifdef CONFIG_LOCKDEP_CROSSRELEASE
> +#define MAX_XHLOCKS_NR 64UL
> + struct hist_lock *xhlocks; /* Crossrelease history locks */
> + unsigned int xhlock_idx;
> + unsigned int xhlock_idx_soft; /* For backing up at softirq entry */
> + unsigned int xhlock_idx_hard; /* For backing up at hardirq entry */
> + unsigned int work_id;
> +#endif
>  #ifdef CONFIG_UBSAN
>   unsigned int in_ubsan;
>  #endif

> +/*
> + * Crossrelease needs to distinguish each work of workqueues.
> + * Caller is supposed to be a worker.
> + */
> +void crossrelease_work_start(void)
> +{
> + if (current->xhlocks)
> + current->work_id++;
> +}

> +/*
> + * Only access local task's data, so irq disable is only required.
> + */
> +static int same_context_xhlock(struct hist_lock *xhlock)
> +{
> + struct task_struct *curr = current;
> +
> + /* In the case of hardirq context */
> + if (curr->hardirq_context) {
> + if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> + return 1;
> + /* In the case of softriq context */
> + } else if (curr->softirq_context) {
> + if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> + return 1;
> + /* In the case of process context */
> + } else {
> + if (xhlock->work_id == curr->work_id)
> + return 1;
> + }
> + return 0;
> +}

I still don't like work_id; it doesn't have anything to do with
workqueues per se, other than the fact that they end up using it.

It's a history generation id; touching it completely invalidates our
history. Workqueues need this because they run independent work from the
same context.

But the same is true for other sites. Last time I suggested
lockdep_assert_empty() to denote all suck places (and note we already
have lockdep_sys_exit() that hooks into the return to user path).

Re: [PATCH v6 05/15] lockdep: Implement crossrelease feature

[Peter Zijlstra]

On Tue, Mar 14, 2017 at 05:18:52PM +0900, Byungchul Park wrote:
> +struct hist_lock {
> + /*
> +  * Each work of workqueue might run in a different context,
> +  * thanks to concurrency support of workqueue. So we have to
> +  * distinguish each work to avoid false positive.
> +  */
> + unsigned intwork_id;
>  };

> @@ -1749,6 +1749,14 @@ struct task_struct {
>   struct held_lock held_locks[MAX_LOCK_DEPTH];
>   gfp_t lockdep_reclaim_gfp;
>  #endif
> +#ifdef CONFIG_LOCKDEP_CROSSRELEASE
> +#define MAX_XHLOCKS_NR 64UL
> + struct hist_lock *xhlocks; /* Crossrelease history locks */
> + unsigned int xhlock_idx;
> + unsigned int xhlock_idx_soft; /* For backing up at softirq entry */
> + unsigned int xhlock_idx_hard; /* For backing up at hardirq entry */
> + unsigned int work_id;
> +#endif
>  #ifdef CONFIG_UBSAN
>   unsigned int in_ubsan;
>  #endif

> +/*
> + * Crossrelease needs to distinguish each work of workqueues.
> + * Caller is supposed to be a worker.
> + */
> +void crossrelease_work_start(void)
> +{
> + if (current->xhlocks)
> + current->work_id++;
> +}

> +/*
> + * Only access local task's data, so irq disable is only required.
> + */
> +static int same_context_xhlock(struct hist_lock *xhlock)
> +{
> + struct task_struct *curr = current;
> +
> + /* In the case of hardirq context */
> + if (curr->hardirq_context) {
> + if (xhlock->hlock.irq_context & 2) /* 2: bitmask for hardirq */
> + return 1;
> + /* In the case of softriq context */
> + } else if (curr->softirq_context) {
> + if (xhlock->hlock.irq_context & 1) /* 1: bitmask for softirq */
> + return 1;
> + /* In the case of process context */
> + } else {
> + if (xhlock->work_id == curr->work_id)
> + return 1;
> + }
> + return 0;
> +}

I still don't like work_id; it doesn't have anything to do with
workqueues per se, other than the fact that they end up using it.

It's a history generation id; touching it completely invalidates our
history. Workqueues need this because they run independent work from the
same context.

But the same is true for other sites. Last time I suggested
lockdep_assert_empty() to denote all suck places (and note we already
have lockdep_sys_exit() that hooks into the return to user path).

[PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

Lockdep is a runtime locking correctness validator that detects and
reports a deadlock or its possibility by checking dependencies between
locks. It's useful since it does not report just an actual deadlock but
also the possibility of a deadlock that has not actually happened yet.
That enables problems to be fixed before they affect real systems.

However, this facility is only applicable to typical locks, such as
spinlocks and mutexes, which are normally released within the context in
which they were acquired. However, synchronization primitives like page
locks or completions, which are allowed to be released in any context,
also create dependencies and can cause a deadlock. So lockdep should
track these locks to do a better job. The 'crossrelease' implementation
makes these primitives also be tracked.

Signed-off-by: Byungchul Park 
---
 include/linux/irqflags.h |  24 ++-
 include/linux/lockdep.h  | 116 +++-
 include/linux/sched.h|   8 +
 kernel/exit.c|   1 +
 kernel/fork.c|   3 +
 kernel/locking/lockdep.c | 451 ---
 kernel/workqueue.c   |   1 +
 lib/Kconfig.debug|  12 ++
 8 files changed, 582 insertions(+), 34 deletions(-)

diff --git a/include/linux/irqflags.h b/include/linux/irqflags.h
index 5dd1272..c40af8a 100644
--- a/include/linux/irqflags.h
+++ b/include/linux/irqflags.h
@@ -23,10 +23,26 @@
 # define trace_softirq_context(p)  ((p)->softirq_context)
 # define trace_hardirqs_enabled(p) ((p)->hardirqs_enabled)
 # define trace_softirqs_enabled(p) ((p)->softirqs_enabled)
-# define trace_hardirq_enter() do { current->hardirq_context++; } while (0)
-# define trace_hardirq_exit()  do { current->hardirq_context--; } while (0)
-# define lockdep_softirq_enter()   do { current->softirq_context++; } 
while (0)
-# define lockdep_softirq_exit()do { current->softirq_context--; } 
while (0)
+# define trace_hardirq_enter() \
+do {   \
+   current->hardirq_context++; \
+   crossrelease_hardirq_start();   \
+} while (0)
+# define trace_hardirq_exit()  \
+do {   \
+   current->hardirq_context--; \
+   crossrelease_hardirq_end(); \
+} while (0)
+# define lockdep_softirq_enter()   \
+do {   \
+   current->softirq_context++; \
+   crossrelease_softirq_start();   \
+} while (0)
+# define lockdep_softirq_exit()\
+do {   \
+   current->softirq_context--; \
+   crossrelease_softirq_end(); \
+} while (0)
 # define INIT_TRACE_IRQFLAGS   .softirqs_enabled = 1,
 #else
 # define trace_hardirqs_on()   do { } while (0)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index c1458fe..9902b2a 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -155,6 +155,12 @@ struct lockdep_map {
int cpu;
unsigned long   ip;
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+   /*
+* Whether it's a crosslock.
+*/
+   int cross;
+#endif
 };
 
 static inline void lockdep_copy_map(struct lockdep_map *to,
@@ -258,9 +264,70 @@ struct held_lock {
unsigned int hardirqs_off:1;
unsigned int references:12; /* 32 
bits */
unsigned int pin_count;
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+   /*
+* Generation id.
+*
+* A value of cross_gen_id will be stored when holding this,
+* which is globally increased whenever each crosslock is held.
+*/
+   unsigned int gen_id;
+#endif
+};
+
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+#define MAX_XHLOCK_TRACE_ENTRIES 5
+
+/*
+ * This is for keeping locks waiting for commit so that true dependencies
+ * can be added at commit step.
+ */
+struct hist_lock {
+   /*
+* Each work of workqueue might run in a different context,
+* thanks to concurrency support of workqueue. So we have to
+* distinguish each work to avoid false positive.
+*/
+   unsigned intwork_id;
+
+   /*
+* Seperate stack_trace data. This will be used at commit step.
+*/
+   struct stack_trace  trace;
+   unsigned long   trace_entries[MAX_XHLOCK_TRACE_ENTRIES];
+
+   /*
+* Seperate hlock instance. This will be used at commit step.
+*
+* TODO: Use a smaller data structure containing only necessary
+* data. However, we should make lockdep code able to handle the
+* smaller one first.
+*/
+   struct held_lockhlock;
 };
 
 /*
+ * To initialize a lock as crosslock, lockdep_init_map_crosslock() should
+ * be called instead of lockdep_init_map().
+ */
+struct cross_lock {
+   /*
+* Seperate hlock instance. This 

[PATCH v6 05/15] lockdep: Implement crossrelease feature

[Byungchul Park]

Lockdep is a runtime locking correctness validator that detects and
reports a deadlock or its possibility by checking dependencies between
locks. It's useful since it does not report just an actual deadlock but
also the possibility of a deadlock that has not actually happened yet.
That enables problems to be fixed before they affect real systems.

However, this facility is only applicable to typical locks, such as
spinlocks and mutexes, which are normally released within the context in
which they were acquired. However, synchronization primitives like page
locks or completions, which are allowed to be released in any context,
also create dependencies and can cause a deadlock. So lockdep should
track these locks to do a better job. The 'crossrelease' implementation
makes these primitives also be tracked.

Signed-off-by: Byungchul Park 
---
 include/linux/irqflags.h |  24 ++-
 include/linux/lockdep.h  | 116 +++-
 include/linux/sched.h|   8 +
 kernel/exit.c|   1 +
 kernel/fork.c|   3 +
 kernel/locking/lockdep.c | 451 ---
 kernel/workqueue.c   |   1 +
 lib/Kconfig.debug|  12 ++
 8 files changed, 582 insertions(+), 34 deletions(-)

diff --git a/include/linux/irqflags.h b/include/linux/irqflags.h
index 5dd1272..c40af8a 100644
--- a/include/linux/irqflags.h
+++ b/include/linux/irqflags.h
@@ -23,10 +23,26 @@
 # define trace_softirq_context(p)  ((p)->softirq_context)
 # define trace_hardirqs_enabled(p) ((p)->hardirqs_enabled)
 # define trace_softirqs_enabled(p) ((p)->softirqs_enabled)
-# define trace_hardirq_enter() do { current->hardirq_context++; } while (0)
-# define trace_hardirq_exit()  do { current->hardirq_context--; } while (0)
-# define lockdep_softirq_enter()   do { current->softirq_context++; } 
while (0)
-# define lockdep_softirq_exit()do { current->softirq_context--; } 
while (0)
+# define trace_hardirq_enter() \
+do {   \
+   current->hardirq_context++; \
+   crossrelease_hardirq_start();   \
+} while (0)
+# define trace_hardirq_exit()  \
+do {   \
+   current->hardirq_context--; \
+   crossrelease_hardirq_end(); \
+} while (0)
+# define lockdep_softirq_enter()   \
+do {   \
+   current->softirq_context++; \
+   crossrelease_softirq_start();   \
+} while (0)
+# define lockdep_softirq_exit()\
+do {   \
+   current->softirq_context--; \
+   crossrelease_softirq_end(); \
+} while (0)
 # define INIT_TRACE_IRQFLAGS   .softirqs_enabled = 1,
 #else
 # define trace_hardirqs_on()   do { } while (0)
diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index c1458fe..9902b2a 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -155,6 +155,12 @@ struct lockdep_map {
int cpu;
unsigned long   ip;
 #endif
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+   /*
+* Whether it's a crosslock.
+*/
+   int cross;
+#endif
 };
 
 static inline void lockdep_copy_map(struct lockdep_map *to,
@@ -258,9 +264,70 @@ struct held_lock {
unsigned int hardirqs_off:1;
unsigned int references:12; /* 32 
bits */
unsigned int pin_count;
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+   /*
+* Generation id.
+*
+* A value of cross_gen_id will be stored when holding this,
+* which is globally increased whenever each crosslock is held.
+*/
+   unsigned int gen_id;
+#endif
+};
+
+#ifdef CONFIG_LOCKDEP_CROSSRELEASE
+#define MAX_XHLOCK_TRACE_ENTRIES 5
+
+/*
+ * This is for keeping locks waiting for commit so that true dependencies
+ * can be added at commit step.
+ */
+struct hist_lock {
+   /*
+* Each work of workqueue might run in a different context,
+* thanks to concurrency support of workqueue. So we have to
+* distinguish each work to avoid false positive.
+*/
+   unsigned intwork_id;
+
+   /*
+* Seperate stack_trace data. This will be used at commit step.
+*/
+   struct stack_trace  trace;
+   unsigned long   trace_entries[MAX_XHLOCK_TRACE_ENTRIES];
+
+   /*
+* Seperate hlock instance. This will be used at commit step.
+*
+* TODO: Use a smaller data structure containing only necessary
+* data. However, we should make lockdep code able to handle the
+* smaller one first.
+*/
+   struct held_lockhlock;
 };
 
 /*
+ * To initialize a lock as crosslock, lockdep_init_map_crosslock() should
+ * be called instead of lockdep_init_map().
+ */
+struct cross_lock {
+   /*
+* Seperate hlock instance. This will be used at commit