Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Mon, Aug 14, 2017 at 03:05:22PM +0800, Boqun Feng wrote:
> > 1. Boqun's approach
> 
> My approach requires(additionally):
> 
>   MAX_XHLOCKS_NR * sizeof(unsigned int) // because of the hist_id field 
> in hist_lock
> 
> bytes per task.
> 
> > 2. Peterz's approach
> 
> And Peter's approach requires(additionally):
> 
>   1 * sizeof(unsigned int)
> 
> bytes per task.
> 
> So basically we need some tradeoff between memory footprints and history
> precision here.

I see what you intended. Then, Peterz's one looks better.

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Mon, Aug 14, 2017 at 03:05:22PM +0800, Boqun Feng wrote:
> > 1. Boqun's approach
> 
> My approach requires(additionally):
> 
>   MAX_XHLOCKS_NR * sizeof(unsigned int) // because of the hist_id field 
> in hist_lock
> 
> bytes per task.
> 
> > 2. Peterz's approach
> 
> And Peter's approach requires(additionally):
> 
>   1 * sizeof(unsigned int)
> 
> bytes per task.
> 
> So basically we need some tradeoff between memory footprints and history
> precision here.

I see what you intended. Then, Peterz's one looks better.

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Mon, Aug 14, 2017 at 03:05:22PM +0800, Boqun Feng wrote:
> > I like Boqun's approach most but, _whatever_. It's ok if it solves the 
> > problem.
> > The last one is not bad when it is used for syscall exit, but we have to 
> > give
> > up valid dependencies unnecessarily in other cases. And I think Peterz's
> > approach should be modified a bit to make it work neatly, like:
> > 
> > crossrelease_hist_end(...)
> > {
> > ...
> >invalidate_xhlock((cur->xhlock_idx_max));
> > 
> >for (c = 0; c < XHLOCK_CXT_NR; c++)
> >   if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
> > MAX_XHLOCKS_NR)
> >  invalidate_xhlock((cur->xhlock_idx_hist[c]));
> > ...
> > }
> > 
> 
> Haven't looked into this deeply, but my gut feeling is this is
> unnecessary, will have a deep look.

Of course, for now, it looks like we can rely on the check_same_context()
on the commit, without invalidating it. But I think the approach might be
dangerous in future. I think it would be better to do it explicitlly.

> 
> Regards,
> Boqun
> 
> > And then Peterz's approach can also work, I think.
> > 
> > ---
> > Thanks,
> > Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Mon, Aug 14, 2017 at 03:05:22PM +0800, Boqun Feng wrote:
> > I like Boqun's approach most but, _whatever_. It's ok if it solves the 
> > problem.
> > The last one is not bad when it is used for syscall exit, but we have to 
> > give
> > up valid dependencies unnecessarily in other cases. And I think Peterz's
> > approach should be modified a bit to make it work neatly, like:
> > 
> > crossrelease_hist_end(...)
> > {
> > ...
> >invalidate_xhlock((cur->xhlock_idx_max));
> > 
> >for (c = 0; c < XHLOCK_CXT_NR; c++)
> >   if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
> > MAX_XHLOCKS_NR)
> >  invalidate_xhlock((cur->xhlock_idx_hist[c]));
> > ...
> > }
> > 
> 
> Haven't looked into this deeply, but my gut feeling is this is
> unnecessary, will have a deep look.

Of course, for now, it looks like we can rely on the check_same_context()
on the commit, without invalidating it. But I think the approach might be
dangerous in future. I think it would be better to do it explicitlly.

> 
> Regards,
> Boqun
> 
> > And then Peterz's approach can also work, I think.
> > 
> > ---
> > Thanks,
> > Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Fri, Aug 11, 2017 at 10:06:37PM +0900, Byungchul Park wrote:
> On Fri, Aug 11, 2017 at 6:44 PM, Byungchul Park  
> wrote:
> > On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
> >> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> >> > Thanks for taking a look at it ;-)
> >>
> >> I rather appriciate it.
> >>
> >> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock 
> >> > > > *xlock, struct hist_lock *xhlock)
> >> > > >  static void commit_xhlocks(struct cross_lock *xlock)
> >> > > >  {
> >> > > > unsigned int cur = current->xhlock_idx;
> >> > > > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
> >> > > > +   unsigned int prev_hist_id = cur + 1;
> >> > >
> >> > > I should have named it another. Could you suggest a better one?
> >> > >
> >> >
> >> > I think "prev" is fine, because I thought the "previous" means the
> >> > xhlock item we visit _previously_.
> >> >
> >> > > > unsigned int i;
> >> > > >
> >> > > > if (!graph_lock())
> >> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock 
> >> > > > *xlock)
> >> > > >  * hist_id than the following one, which is 
> >> > > > impossible
> >> > > >  * otherwise.
> >> > >
> >> > > Or we need to modify the comment so that the word 'prev' does not make
> >> > > readers confused. It was my mistake.
> >> > >
> >> >
> >> > I think the comment needs some help, but before you do it, could you
> >> > have another look at what Peter proposed previously? Note you have a
> >> > same_context_xhlock() check in the commit_xhlocks(), so the your
> >> > previous overwrite case actually could be detected, I think.
> >>
> >> What is the previous overwrite case?
> >>
> >> ppi
> >> iii
> >>
> >> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
> >> peterz's suggestion also seems to work.
> >>
> >> > However, one thing may not be detected is this case:
> >> >
> >> > pp
> >> > wrapped >   www
> >>
> >> To be honest, I think your suggestion is more natual, with which this
> >> case would be also covered.
> >>
> >> >
> >> > where p: process and w: worker.
> >> >
> >> > , because p and w are in the same task_irq_context(). I discussed this
> >> > with Peter yesterday, and he has a good idea: unconditionally do a reset
> >> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
> >
> > Ah, ok. You meant 'whenever _process_ context exit'.
> >
> > I need more time to be sure, but anyway for now it seems to work with
> > giving up some chances for remaining xhlocks.
> >
> > But, I am not sure if it's still true even in future and the code can be
> > maintained easily. I think your approach is natural and neat enough for
> > that purpose. What problem exists with yours?
> 

My approach works but it has bigger memmory footprint than Peter's, so I
asked about whether you could consider Peter's approach.

> Let me list up the possible approaches:
> 
> 0. Byungchul's approach

Your approach requires(additionally):

MAX_XHLOCKS_NR * sizeof(unsigned int) // because of the hist_id field 
in hist_lock
+ 
(XHLOCK_CXT_NR + 1) * sizeof(unsigned int) // because of fields in 
task_struct

bytes per task.

> 1. Boqun's approach

My approach requires(additionally):

MAX_XHLOCKS_NR * sizeof(unsigned int) // because of the hist_id field 
in hist_lock

bytes per task.

> 2. Peterz's approach

And Peter's approach requires(additionally):

1 * sizeof(unsigned int)

bytes per task.

So basically we need some tradeoff between memory footprints and history
precision here.

> 3. Reset on process exit
> 
> I like Boqun's approach most but, _whatever_. It's ok if it solves the 
> problem.
> The last one is not bad when it is used for syscall exit, but we have to give
> up valid dependencies unnecessarily in other cases. And I think Peterz's
> approach should be modified a bit to make it work neatly, like:
> 
> crossrelease_hist_end(...)
> {
> ...
>invalidate_xhlock((cur->xhlock_idx_max));
> 
>for (c = 0; c < XHLOCK_CXT_NR; c++)
>   if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
> MAX_XHLOCKS_NR)
>  invalidate_xhlock((cur->xhlock_idx_hist[c]));
> ...
> }
> 

Haven't looked into this deeply, but my gut feeling is this is
unnecessary, will have a deep look.

Regards,
Boqun

> And then Peterz's approach can also work, I think.
> 
> ---
> Thanks,
> Byungchul


signature.asc
Description: PGP signature

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Fri, Aug 11, 2017 at 10:06:37PM +0900, Byungchul Park wrote:
> On Fri, Aug 11, 2017 at 6:44 PM, Byungchul Park  
> wrote:
> > On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
> >> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> >> > Thanks for taking a look at it ;-)
> >>
> >> I rather appriciate it.
> >>
> >> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock 
> >> > > > *xlock, struct hist_lock *xhlock)
> >> > > >  static void commit_xhlocks(struct cross_lock *xlock)
> >> > > >  {
> >> > > > unsigned int cur = current->xhlock_idx;
> >> > > > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
> >> > > > +   unsigned int prev_hist_id = cur + 1;
> >> > >
> >> > > I should have named it another. Could you suggest a better one?
> >> > >
> >> >
> >> > I think "prev" is fine, because I thought the "previous" means the
> >> > xhlock item we visit _previously_.
> >> >
> >> > > > unsigned int i;
> >> > > >
> >> > > > if (!graph_lock())
> >> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock 
> >> > > > *xlock)
> >> > > >  * hist_id than the following one, which is 
> >> > > > impossible
> >> > > >  * otherwise.
> >> > >
> >> > > Or we need to modify the comment so that the word 'prev' does not make
> >> > > readers confused. It was my mistake.
> >> > >
> >> >
> >> > I think the comment needs some help, but before you do it, could you
> >> > have another look at what Peter proposed previously? Note you have a
> >> > same_context_xhlock() check in the commit_xhlocks(), so the your
> >> > previous overwrite case actually could be detected, I think.
> >>
> >> What is the previous overwrite case?
> >>
> >> ppi
> >> iii
> >>
> >> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
> >> peterz's suggestion also seems to work.
> >>
> >> > However, one thing may not be detected is this case:
> >> >
> >> > pp
> >> > wrapped >   www
> >>
> >> To be honest, I think your suggestion is more natual, with which this
> >> case would be also covered.
> >>
> >> >
> >> > where p: process and w: worker.
> >> >
> >> > , because p and w are in the same task_irq_context(). I discussed this
> >> > with Peter yesterday, and he has a good idea: unconditionally do a reset
> >> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
> >
> > Ah, ok. You meant 'whenever _process_ context exit'.
> >
> > I need more time to be sure, but anyway for now it seems to work with
> > giving up some chances for remaining xhlocks.
> >
> > But, I am not sure if it's still true even in future and the code can be
> > maintained easily. I think your approach is natural and neat enough for
> > that purpose. What problem exists with yours?
> 

My approach works but it has bigger memmory footprint than Peter's, so I
asked about whether you could consider Peter's approach.

> Let me list up the possible approaches:
> 
> 0. Byungchul's approach

Your approach requires(additionally):

MAX_XHLOCKS_NR * sizeof(unsigned int) // because of the hist_id field 
in hist_lock
+ 
(XHLOCK_CXT_NR + 1) * sizeof(unsigned int) // because of fields in 
task_struct

bytes per task.

> 1. Boqun's approach

My approach requires(additionally):

MAX_XHLOCKS_NR * sizeof(unsigned int) // because of the hist_id field 
in hist_lock

bytes per task.

> 2. Peterz's approach

And Peter's approach requires(additionally):

1 * sizeof(unsigned int)

bytes per task.

So basically we need some tradeoff between memory footprints and history
precision here.

> 3. Reset on process exit
> 
> I like Boqun's approach most but, _whatever_. It's ok if it solves the 
> problem.
> The last one is not bad when it is used for syscall exit, but we have to give
> up valid dependencies unnecessarily in other cases. And I think Peterz's
> approach should be modified a bit to make it work neatly, like:
> 
> crossrelease_hist_end(...)
> {
> ...
>invalidate_xhlock((cur->xhlock_idx_max));
> 
>for (c = 0; c < XHLOCK_CXT_NR; c++)
>   if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
> MAX_XHLOCKS_NR)
>  invalidate_xhlock((cur->xhlock_idx_hist[c]));
> ...
> }
> 

Haven't looked into this deeply, but my gut feeling is this is
unnecessary, will have a deep look.

Regards,
Boqun

> And then Peterz's approach can also work, I think.
> 
> ---
> Thanks,
> Byungchul


signature.asc
Description: PGP signature

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Fri, Aug 11, 2017 at 6:44 PM, Byungchul Park  wrote:
> On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
>> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
>> > Thanks for taking a look at it ;-)
>>
>> I rather appriciate it.
>>
>> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock 
>> > > > *xlock, struct hist_lock *xhlock)
>> > > >  static void commit_xhlocks(struct cross_lock *xlock)
>> > > >  {
>> > > > unsigned int cur = current->xhlock_idx;
>> > > > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
>> > > > +   unsigned int prev_hist_id = cur + 1;
>> > >
>> > > I should have named it another. Could you suggest a better one?
>> > >
>> >
>> > I think "prev" is fine, because I thought the "previous" means the
>> > xhlock item we visit _previously_.
>> >
>> > > > unsigned int i;
>> > > >
>> > > > if (!graph_lock())
>> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock 
>> > > > *xlock)
>> > > >  * hist_id than the following one, which is 
>> > > > impossible
>> > > >  * otherwise.
>> > >
>> > > Or we need to modify the comment so that the word 'prev' does not make
>> > > readers confused. It was my mistake.
>> > >
>> >
>> > I think the comment needs some help, but before you do it, could you
>> > have another look at what Peter proposed previously? Note you have a
>> > same_context_xhlock() check in the commit_xhlocks(), so the your
>> > previous overwrite case actually could be detected, I think.
>>
>> What is the previous overwrite case?
>>
>> ppi
>> iii
>>
>> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
>> peterz's suggestion also seems to work.
>>
>> > However, one thing may not be detected is this case:
>> >
>> > pp
>> > wrapped >   www
>>
>> To be honest, I think your suggestion is more natual, with which this
>> case would be also covered.
>>
>> >
>> > where p: process and w: worker.
>> >
>> > , because p and w are in the same task_irq_context(). I discussed this
>> > with Peter yesterday, and he has a good idea: unconditionally do a reset
>> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
>
> Ah, ok. You meant 'whenever _process_ context exit'.
>
> I need more time to be sure, but anyway for now it seems to work with
> giving up some chances for remaining xhlocks.
>
> But, I am not sure if it's still true even in future and the code can be
> maintained easily. I think your approach is natural and neat enough for
> that purpose. What problem exists with yours?

Let me list up the possible approaches:

0. Byungchul's approach
1. Boqun's approach
2. Peterz's approach
3. Reset on process exit

I like Boqun's approach most but, _whatever_. It's ok if it solves the problem.
The last one is not bad when it is used for syscall exit, but we have to give
up valid dependencies unnecessarily in other cases. And I think Peterz's
approach should be modified a bit to make it work neatly, like:

crossrelease_hist_end(...)
{
...
   invalidate_xhlock((cur->xhlock_idx_max));

   for (c = 0; c < XHLOCK_CXT_NR; c++)
  if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
MAX_XHLOCKS_NR)
 invalidate_xhlock((cur->xhlock_idx_hist[c]));
...
}

And then Peterz's approach can also work, I think.

---
Thanks,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Fri, Aug 11, 2017 at 6:44 PM, Byungchul Park  wrote:
> On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
>> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
>> > Thanks for taking a look at it ;-)
>>
>> I rather appriciate it.
>>
>> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock 
>> > > > *xlock, struct hist_lock *xhlock)
>> > > >  static void commit_xhlocks(struct cross_lock *xlock)
>> > > >  {
>> > > > unsigned int cur = current->xhlock_idx;
>> > > > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
>> > > > +   unsigned int prev_hist_id = cur + 1;
>> > >
>> > > I should have named it another. Could you suggest a better one?
>> > >
>> >
>> > I think "prev" is fine, because I thought the "previous" means the
>> > xhlock item we visit _previously_.
>> >
>> > > > unsigned int i;
>> > > >
>> > > > if (!graph_lock())
>> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock 
>> > > > *xlock)
>> > > >  * hist_id than the following one, which is 
>> > > > impossible
>> > > >  * otherwise.
>> > >
>> > > Or we need to modify the comment so that the word 'prev' does not make
>> > > readers confused. It was my mistake.
>> > >
>> >
>> > I think the comment needs some help, but before you do it, could you
>> > have another look at what Peter proposed previously? Note you have a
>> > same_context_xhlock() check in the commit_xhlocks(), so the your
>> > previous overwrite case actually could be detected, I think.
>>
>> What is the previous overwrite case?
>>
>> ppi
>> iii
>>
>> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
>> peterz's suggestion also seems to work.
>>
>> > However, one thing may not be detected is this case:
>> >
>> > pp
>> > wrapped >   www
>>
>> To be honest, I think your suggestion is more natual, with which this
>> case would be also covered.
>>
>> >
>> > where p: process and w: worker.
>> >
>> > , because p and w are in the same task_irq_context(). I discussed this
>> > with Peter yesterday, and he has a good idea: unconditionally do a reset
>> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
>
> Ah, ok. You meant 'whenever _process_ context exit'.
>
> I need more time to be sure, but anyway for now it seems to work with
> giving up some chances for remaining xhlocks.
>
> But, I am not sure if it's still true even in future and the code can be
> maintained easily. I think your approach is natural and neat enough for
> that purpose. What problem exists with yours?

Let me list up the possible approaches:

0. Byungchul's approach
1. Boqun's approach
2. Peterz's approach
3. Reset on process exit

I like Boqun's approach most but, _whatever_. It's ok if it solves the problem.
The last one is not bad when it is used for syscall exit, but we have to give
up valid dependencies unnecessarily in other cases. And I think Peterz's
approach should be modified a bit to make it work neatly, like:

crossrelease_hist_end(...)
{
...
   invalidate_xhlock((cur->xhlock_idx_max));

   for (c = 0; c < XHLOCK_CXT_NR; c++)
  if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
MAX_XHLOCKS_NR)
 invalidate_xhlock((cur->xhlock_idx_hist[c]));
...
}

And then Peterz's approach can also work, I think.

---
Thanks,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> > Thanks for taking a look at it ;-)
> 
> I rather appriciate it.
> 
> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock 
> > > > *xlock, struct hist_lock *xhlock)
> > > >  static void commit_xhlocks(struct cross_lock *xlock)
> > > >  {
> > > > unsigned int cur = current->xhlock_idx;
> > > > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
> > > > +   unsigned int prev_hist_id = cur + 1;
> > > 
> > > I should have named it another. Could you suggest a better one?
> > > 
> > 
> > I think "prev" is fine, because I thought the "previous" means the
> > xhlock item we visit _previously_.
> > 
> > > > unsigned int i;
> > > >  
> > > > if (!graph_lock())
> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock 
> > > > *xlock)
> > > >  * hist_id than the following one, which is 
> > > > impossible
> > > >  * otherwise.
> > > 
> > > Or we need to modify the comment so that the word 'prev' does not make
> > > readers confused. It was my mistake.
> > > 
> > 
> > I think the comment needs some help, but before you do it, could you
> > have another look at what Peter proposed previously? Note you have a
> > same_context_xhlock() check in the commit_xhlocks(), so the your
> > previous overwrite case actually could be detected, I think.
> 
> What is the previous overwrite case?
> 
> ppi
> iii
> 
> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
> peterz's suggestion also seems to work.
> 
> > However, one thing may not be detected is this case:
> > 
> > pp
> > wrapped >   www
> 
> To be honest, I think your suggestion is more natual, with which this
> case would be also covered.
> 
> > 
> > where p: process and w: worker.
> > 
> > , because p and w are in the same task_irq_context(). I discussed this
> > with Peter yesterday, and he has a good idea: unconditionally do a reset
> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).

Ah, ok. You meant 'whenever _process_ context exit'.

I need more time to be sure, but anyway for now it seems to work with
giving up some chances for remaining xhlocks.

But, I am not sure if it's still true even in future and the code can be
maintained easily. I think your approach is natural and neat enough for
that purpose. What problem exists with yours?

> > Basically it means we empty the lock history whenever we finished a
> > worker function in a worker thread or we are about to return to
> > userspace after we finish the syscall. This could further save some
> > memory and so I think this may be better than my approach.
> 
> Do you mean reset _whenever_ hard irq exit, soft irq exit or work exit?
> Why should we give up chances to check dependencies of remaining xhlocks
> whenever each exit? Am I understanding correctly?
> 
> I am just curious. Does your approach have some problems?
> 
> Thanks,
> Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> > Thanks for taking a look at it ;-)
> 
> I rather appriciate it.
> 
> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock 
> > > > *xlock, struct hist_lock *xhlock)
> > > >  static void commit_xhlocks(struct cross_lock *xlock)
> > > >  {
> > > > unsigned int cur = current->xhlock_idx;
> > > > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
> > > > +   unsigned int prev_hist_id = cur + 1;
> > > 
> > > I should have named it another. Could you suggest a better one?
> > > 
> > 
> > I think "prev" is fine, because I thought the "previous" means the
> > xhlock item we visit _previously_.
> > 
> > > > unsigned int i;
> > > >  
> > > > if (!graph_lock())
> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock 
> > > > *xlock)
> > > >  * hist_id than the following one, which is 
> > > > impossible
> > > >  * otherwise.
> > > 
> > > Or we need to modify the comment so that the word 'prev' does not make
> > > readers confused. It was my mistake.
> > > 
> > 
> > I think the comment needs some help, but before you do it, could you
> > have another look at what Peter proposed previously? Note you have a
> > same_context_xhlock() check in the commit_xhlocks(), so the your
> > previous overwrite case actually could be detected, I think.
> 
> What is the previous overwrite case?
> 
> ppi
> iii
> 
> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
> peterz's suggestion also seems to work.
> 
> > However, one thing may not be detected is this case:
> > 
> > pp
> > wrapped >   www
> 
> To be honest, I think your suggestion is more natual, with which this
> case would be also covered.
> 
> > 
> > where p: process and w: worker.
> > 
> > , because p and w are in the same task_irq_context(). I discussed this
> > with Peter yesterday, and he has a good idea: unconditionally do a reset
> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).

Ah, ok. You meant 'whenever _process_ context exit'.

I need more time to be sure, but anyway for now it seems to work with
giving up some chances for remaining xhlocks.

But, I am not sure if it's still true even in future and the code can be
maintained easily. I think your approach is natural and neat enough for
that purpose. What problem exists with yours?

> > Basically it means we empty the lock history whenever we finished a
> > worker function in a worker thread or we are about to return to
> > userspace after we finish the syscall. This could further save some
> > memory and so I think this may be better than my approach.
> 
> Do you mean reset _whenever_ hard irq exit, soft irq exit or work exit?
> Why should we give up chances to check dependencies of remaining xhlocks
> whenever each exit? Am I understanding correctly?
> 
> I am just curious. Does your approach have some problems?
> 
> Thanks,
> Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> Thanks for taking a look at it ;-)

I rather appriciate it.

> > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> > > struct hist_lock *xhlock)
> > >  static void commit_xhlocks(struct cross_lock *xlock)
> > >  {
> > >   unsigned int cur = current->xhlock_idx;
> > > - unsigned int prev_hist_id = xhlock(cur).hist_id;
> > > + unsigned int prev_hist_id = cur + 1;
> > 
> > I should have named it another. Could you suggest a better one?
> > 
> 
> I think "prev" is fine, because I thought the "previous" means the
> xhlock item we visit _previously_.
> 
> > >   unsigned int i;
> > >  
> > >   if (!graph_lock())
> > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> > >* hist_id than the following one, which is impossible
> > >* otherwise.
> > 
> > Or we need to modify the comment so that the word 'prev' does not make
> > readers confused. It was my mistake.
> > 
> 
> I think the comment needs some help, but before you do it, could you
> have another look at what Peter proposed previously? Note you have a
> same_context_xhlock() check in the commit_xhlocks(), so the your
> previous overwrite case actually could be detected, I think.

What is the previous overwrite case?

ppi
iii

Do you mean this one? I missed the check of same_context_xhlock(). Yes,
peterz's suggestion also seems to work.

> However, one thing may not be detected is this case:
> 
>   pp
> wrapped > www

To be honest, I think your suggestion is more natual, with which this
case would be also covered.

> 
>   where p: process and w: worker.
> 
> , because p and w are in the same task_irq_context(). I discussed this
> with Peter yesterday, and he has a good idea: unconditionally do a reset
> on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
> Basically it means we empty the lock history whenever we finished a
> worker function in a worker thread or we are about to return to
> userspace after we finish the syscall. This could further save some
> memory and so I think this may be better than my approach.

Do you mean reset _whenever_ hard irq exit, soft irq exit or work exit?
Why should we give up chances to check dependencies of remaining xhlocks
whenever each exit? Am I understanding correctly?

I am just curious. Does your approach have some problems?

Thanks,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> Thanks for taking a look at it ;-)

I rather appriciate it.

> > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> > > struct hist_lock *xhlock)
> > >  static void commit_xhlocks(struct cross_lock *xlock)
> > >  {
> > >   unsigned int cur = current->xhlock_idx;
> > > - unsigned int prev_hist_id = xhlock(cur).hist_id;
> > > + unsigned int prev_hist_id = cur + 1;
> > 
> > I should have named it another. Could you suggest a better one?
> > 
> 
> I think "prev" is fine, because I thought the "previous" means the
> xhlock item we visit _previously_.
> 
> > >   unsigned int i;
> > >  
> > >   if (!graph_lock())
> > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> > >* hist_id than the following one, which is impossible
> > >* otherwise.
> > 
> > Or we need to modify the comment so that the word 'prev' does not make
> > readers confused. It was my mistake.
> > 
> 
> I think the comment needs some help, but before you do it, could you
> have another look at what Peter proposed previously? Note you have a
> same_context_xhlock() check in the commit_xhlocks(), so the your
> previous overwrite case actually could be detected, I think.

What is the previous overwrite case?

ppi
iii

Do you mean this one? I missed the check of same_context_xhlock(). Yes,
peterz's suggestion also seems to work.

> However, one thing may not be detected is this case:
> 
>   pp
> wrapped > www

To be honest, I think your suggestion is more natual, with which this
case would be also covered.

> 
>   where p: process and w: worker.
> 
> , because p and w are in the same task_irq_context(). I discussed this
> with Peter yesterday, and he has a good idea: unconditionally do a reset
> on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
> Basically it means we empty the lock history whenever we finished a
> worker function in a worker thread or we are about to return to
> userspace after we finish the syscall. This could further save some
> memory and so I think this may be better than my approach.

Do you mean reset _whenever_ hard irq exit, soft irq exit or work exit?
Why should we give up chances to check dependencies of remaining xhlocks
whenever each exit? Am I understanding correctly?

I am just curious. Does your approach have some problems?

Thanks,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Fri, Aug 11, 2017 at 12:43:28PM +0900, Byungchul Park wrote:
> On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> > > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct 
> > > > > > held_lock
> > > > > *hlock)
> > > > > >   * Check if the xhlock is valid, which would be false if,
> > > > > >   *
> > > > > >   *1. Has not used after initializaion yet.
> > > > > > + *2. Got invalidated.
> > > > > >   *
> > > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > > >   */
> > > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock 
> > > > > > *hlock)
> > > > > >
> > > > > > /* Initialize hist_lock's members */
> > > > > > xhlock->hlock = *hlock;
> > > > > > +   xhlock->hist_id = current->hist_id++;
> > > 
> > > Besides, is this code correct? Does this just make xhlock->hist_id
> > > one-less-than the curr->hist_id, which cause the invalidation every time
> > > you do ring buffer unwinding?
> > > 
> > > Regards,
> > > Boqun
> > > 
> > 
> > So basically, I'm suggesting do this on top of your patch, there is also
> > a fix in commit_xhlocks(), which I think you should swap the parameters
> > in before(...), no matter using task_struct::hist_id or using
> > task_struct::xhlock_idx as the timestamp.
> > 
> > Hope this could make my point more clear, and if I do miss something,
> > please point it out, thanks ;-)
> 
> Sorry for mis-understanding. I like your patch. I think it works.
> 

Thanks for taking a look at it ;-)

> Additionally.. See below..
> 
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 074872f016f8..886ba79bfc38 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -854,9 +854,6 @@ struct task_struct {
> > unsigned int xhlock_idx;
> > /* For restoring at history boundaries */
> > unsigned int xhlock_idx_hist[XHLOCK_NR];
> > -   unsigned int hist_id;
> > -   /* For overwrite check at each context exit */
> > -   unsigned int hist_id_save[XHLOCK_NR];
> >  #endif
> >  
> >  #ifdef CONFIG_UBSAN
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index 699fbeab1920..04c6c8d68e18 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
> >  {
> > struct task_struct *cur = current;
> >  
> > -   if (cur->xhlocks) {
> > +   if (cur->xhlocks)
> > cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> > -   cur->hist_id_save[c] = cur->hist_id;
> > -   }
> >  }
> >  
> >  void crossrelease_hist_end(enum xhlock_context_t c)
> > @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
> > cur->xhlock_idx = idx;
> >  
> > /* Check if the ring was overwritten. */
> > -   if (h->hist_id != cur->hist_id_save[c])
> > +   if (h->hist_id != idx)
> > invalidate_xhlock(h);
> > }
> >  }
> > @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
> >  
> > /* Initialize hist_lock's members */
> > xhlock->hlock = *hlock;
> > -   xhlock->hist_id = current->hist_id++;
> > +   xhlock->hist_id = idx;
> >  
> > xhlock->trace.nr_entries = 0;
> > xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> > struct hist_lock *xhlock)
> >  static void commit_xhlocks(struct cross_lock *xlock)
> >  {
> > unsigned int cur = current->xhlock_idx;
> > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
> > +   unsigned int prev_hist_id = cur + 1;
> 
> I should have named it another. Could you suggest a better one?
> 

I think "prev" is fine, because I thought the "previous" means the
xhlock item we visit _previously_.

> > unsigned int i;
> >  
> > if (!graph_lock())
> > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> >  * hist_id than the following one, which is impossible
> >  * otherwise.
> 
> Or we need to modify the comment so that the word 'prev' does not make
> readers confused. It was my mistake.
> 

I think the comment needs some help, but before you do it, could you
have another look at what Peter proposed previously? Note you have a
same_context_xhlock() check in the commit_xhlocks(), so the your
previous overwrite case actually could be detected, I think.

However, one thing may not be detected is this case:

pp
wrapped >   www

where p: process and w: worker.

, because p and w are in the same task_irq_context(). I discussed this
with Peter yesterday, and he has a good idea: unconditionally do a reset
on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
Basically it means we empty the lock history whenever we finished a
worker function in a worker thread or we are about to return to
userspace after we finish 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Fri, Aug 11, 2017 at 12:43:28PM +0900, Byungchul Park wrote:
> On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> > > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct 
> > > > > > held_lock
> > > > > *hlock)
> > > > > >   * Check if the xhlock is valid, which would be false if,
> > > > > >   *
> > > > > >   *1. Has not used after initializaion yet.
> > > > > > + *2. Got invalidated.
> > > > > >   *
> > > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > > >   */
> > > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock 
> > > > > > *hlock)
> > > > > >
> > > > > > /* Initialize hist_lock's members */
> > > > > > xhlock->hlock = *hlock;
> > > > > > +   xhlock->hist_id = current->hist_id++;
> > > 
> > > Besides, is this code correct? Does this just make xhlock->hist_id
> > > one-less-than the curr->hist_id, which cause the invalidation every time
> > > you do ring buffer unwinding?
> > > 
> > > Regards,
> > > Boqun
> > > 
> > 
> > So basically, I'm suggesting do this on top of your patch, there is also
> > a fix in commit_xhlocks(), which I think you should swap the parameters
> > in before(...), no matter using task_struct::hist_id or using
> > task_struct::xhlock_idx as the timestamp.
> > 
> > Hope this could make my point more clear, and if I do miss something,
> > please point it out, thanks ;-)
> 
> Sorry for mis-understanding. I like your patch. I think it works.
> 

Thanks for taking a look at it ;-)

> Additionally.. See below..
> 
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 074872f016f8..886ba79bfc38 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -854,9 +854,6 @@ struct task_struct {
> > unsigned int xhlock_idx;
> > /* For restoring at history boundaries */
> > unsigned int xhlock_idx_hist[XHLOCK_NR];
> > -   unsigned int hist_id;
> > -   /* For overwrite check at each context exit */
> > -   unsigned int hist_id_save[XHLOCK_NR];
> >  #endif
> >  
> >  #ifdef CONFIG_UBSAN
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index 699fbeab1920..04c6c8d68e18 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
> >  {
> > struct task_struct *cur = current;
> >  
> > -   if (cur->xhlocks) {
> > +   if (cur->xhlocks)
> > cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> > -   cur->hist_id_save[c] = cur->hist_id;
> > -   }
> >  }
> >  
> >  void crossrelease_hist_end(enum xhlock_context_t c)
> > @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
> > cur->xhlock_idx = idx;
> >  
> > /* Check if the ring was overwritten. */
> > -   if (h->hist_id != cur->hist_id_save[c])
> > +   if (h->hist_id != idx)
> > invalidate_xhlock(h);
> > }
> >  }
> > @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
> >  
> > /* Initialize hist_lock's members */
> > xhlock->hlock = *hlock;
> > -   xhlock->hist_id = current->hist_id++;
> > +   xhlock->hist_id = idx;
> >  
> > xhlock->trace.nr_entries = 0;
> > xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> > struct hist_lock *xhlock)
> >  static void commit_xhlocks(struct cross_lock *xlock)
> >  {
> > unsigned int cur = current->xhlock_idx;
> > -   unsigned int prev_hist_id = xhlock(cur).hist_id;
> > +   unsigned int prev_hist_id = cur + 1;
> 
> I should have named it another. Could you suggest a better one?
> 

I think "prev" is fine, because I thought the "previous" means the
xhlock item we visit _previously_.

> > unsigned int i;
> >  
> > if (!graph_lock())
> > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> >  * hist_id than the following one, which is impossible
> >  * otherwise.
> 
> Or we need to modify the comment so that the word 'prev' does not make
> readers confused. It was my mistake.
> 

I think the comment needs some help, but before you do it, could you
have another look at what Peter proposed previously? Note you have a
same_context_xhlock() check in the commit_xhlocks(), so the your
previous overwrite case actually could be detected, I think.

However, one thing may not be detected is this case:

pp
wrapped >   www

where p: process and w: worker.

, because p and w are in the same task_irq_context(). I discussed this
with Peter yesterday, and he has a good idea: unconditionally do a reset
on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
Basically it means we empty the lock history whenever we finished a
worker function in a worker thread or we are about to return to
userspace after we finish 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > *hlock)
> > > > >   * Check if the xhlock is valid, which would be false if,
> > > > >   *
> > > > >   *1. Has not used after initializaion yet.
> > > > > + *2. Got invalidated.
> > > > >   *
> > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > >   */
> > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > >
> > > > >   /* Initialize hist_lock's members */
> > > > >   xhlock->hlock = *hlock;
> > > > > + xhlock->hist_id = current->hist_id++;
> > 
> > Besides, is this code correct? Does this just make xhlock->hist_id
> > one-less-than the curr->hist_id, which cause the invalidation every time
> > you do ring buffer unwinding?
> > 
> > Regards,
> > Boqun
> > 
> 
> So basically, I'm suggesting do this on top of your patch, there is also
> a fix in commit_xhlocks(), which I think you should swap the parameters
> in before(...), no matter using task_struct::hist_id or using
> task_struct::xhlock_idx as the timestamp.
> 
> Hope this could make my point more clear, and if I do miss something,
> please point it out, thanks ;-)

Sorry for mis-understanding. I like your patch. I think it works.

Additionally.. See below..

> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 074872f016f8..886ba79bfc38 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -854,9 +854,6 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 699fbeab1920..04c6c8d68e18 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum xhlock_context_t c)
> @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
>   cur->xhlock_idx = idx;
>  
>   /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> + if (h->hist_id != idx)
>   invalidate_xhlock(h);
>   }
>  }
> @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> - xhlock->hist_id = current->hist_id++;
> + xhlock->hist_id = idx;
>  
>   xhlock->trace.nr_entries = 0;
>   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>   unsigned int cur = current->xhlock_idx;
> - unsigned int prev_hist_id = xhlock(cur).hist_id;
> + unsigned int prev_hist_id = cur + 1;

I should have named it another. Could you suggest a better one?

>   unsigned int i;
>  
>   if (!graph_lock())
> @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>* hist_id than the following one, which is impossible
>* otherwise.

Or we need to modify the comment so that the word 'prev' does not make
readers confused. It was my mistake.

Thanks,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > *hlock)
> > > > >   * Check if the xhlock is valid, which would be false if,
> > > > >   *
> > > > >   *1. Has not used after initializaion yet.
> > > > > + *2. Got invalidated.
> > > > >   *
> > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > >   */
> > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > >
> > > > >   /* Initialize hist_lock's members */
> > > > >   xhlock->hlock = *hlock;
> > > > > + xhlock->hist_id = current->hist_id++;
> > 
> > Besides, is this code correct? Does this just make xhlock->hist_id
> > one-less-than the curr->hist_id, which cause the invalidation every time
> > you do ring buffer unwinding?
> > 
> > Regards,
> > Boqun
> > 
> 
> So basically, I'm suggesting do this on top of your patch, there is also
> a fix in commit_xhlocks(), which I think you should swap the parameters
> in before(...), no matter using task_struct::hist_id or using
> task_struct::xhlock_idx as the timestamp.
> 
> Hope this could make my point more clear, and if I do miss something,
> please point it out, thanks ;-)

Sorry for mis-understanding. I like your patch. I think it works.

Additionally.. See below..

> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 074872f016f8..886ba79bfc38 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -854,9 +854,6 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 699fbeab1920..04c6c8d68e18 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum xhlock_context_t c)
> @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
>   cur->xhlock_idx = idx;
>  
>   /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> + if (h->hist_id != idx)
>   invalidate_xhlock(h);
>   }
>  }
> @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> - xhlock->hist_id = current->hist_id++;
> + xhlock->hist_id = idx;
>  
>   xhlock->trace.nr_entries = 0;
>   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>   unsigned int cur = current->xhlock_idx;
> - unsigned int prev_hist_id = xhlock(cur).hist_id;
> + unsigned int prev_hist_id = cur + 1;

I should have named it another. Could you suggest a better one?

>   unsigned int i;
>  
>   if (!graph_lock())
> @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>* hist_id than the following one, which is impossible
>* otherwise.

Or we need to modify the comment so that the word 'prev' does not make
readers confused. It was my mistake.

Thanks,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Fri, Aug 11, 2017 at 09:40:21AM +0900, Byungchul Park wrote:
> On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
> > > > >  void crossrelease_hist_end(enum context_t c)
> > > > >  {
> > > > > - if (current->xhlocks)
> > > > > - current->xhlock_idx = current->xhlock_idx_hist[c];
> > > > > + struct task_struct *cur = current;
> > > > > +
> > > > > + if (cur->xhlocks) {
> > > > > + unsigned int idx = cur->xhlock_idx_hist[c];
> > > > > + struct hist_lock *h = (idx);
> > > > > +
> > > > > + cur->xhlock_idx = idx;
> > > > > +
> > > > > + /* Check if the ring was overwritten. */
> > > > > + if (h->hist_id != cur->hist_id_save[c])
> > > > 
> > > > Could we use:
> > > > 
> > > > if (h->hist_id != idx)
> > > 
> > > No, we cannot.
> > > 
> > 
> > Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> > are increased at the same place(in add_xhlock()), right?
> 
> Right.
> 
> > And, yes, xhlock_idx will get decreased when we do ring-buffer
> 
> This is why we should keep both of them.
> 
> > unwinding, but that's OK, because we need to throw away those recently
> > added items.
> > 
> > And xhlock_idx always points to the most recently added valid item,
> 
> No, it's not true in case that the ring buffer was wrapped like:
> 
>   
> wrapped > 
>  ^
>  xhlock_idx points here after unwinding,
>  and it's not a valid one.
> 
>   where p represents an acquisition in process context,
>   i represents an acquisition in irq context.
> 

Yeah, but we can detect this with comparison between the
hist_lock::hist_id and the task_struct::xhlock_idx in
commit_xhlocks()(see my patch), no?

Regards,
Boqun

> > right?  Any other item's idx must "before()" the most recently added
> > one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?
> 
> Both of two answers are _no_.
> 
> > Maybe I'm missing something subtle, but could you show me an example,
> > that could end up being a problem if we use xhlock_idx as the hist_id?
> 
> See the example above. We cannot detect whether it was wrapped or not using
> xhlock_idx.
> 
> > 
> > > hist_id is a kind of timestamp and used to detect overwriting
> > > data into places of same indexes of the ring buffer. And idx is
> > > just an index. :) IOW, they mean different things.
> > > 
> > > > 
> > > > here, and
> > > > 
> > > > > + invalidate_xhlock(h);
> > > > > + }
> > > > >  }
> > > > >
> > > > >  static int cross_lock(struct lockdep_map *lock)
> > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > *hlock)
> > > > >   * Check if the xhlock is valid, which would be false if,
> > > > >   *
> > > > >   *1. Has not used after initializaion yet.
> > > > > + *2. Got invalidated.
> > > > >   *
> > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > >   */
> > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > >
> > > > >   /* Initialize hist_lock's members */
> > > > >   xhlock->hlock = *hlock;
> > > > > + xhlock->hist_id = current->hist_id++;
> > 
> > Besides, is this code correct? Does this just make xhlock->hist_id
> > one-less-than the curr->hist_id, which cause the invalidation every time
> > you do ring buffer unwinding?
> 
> Right. "save = hist_id++" should be "save = ++hist_id". Could you fix it?
> 
> Thank you,
> Byungchul
> 


signature.asc
Description: PGP signature

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Fri, Aug 11, 2017 at 09:40:21AM +0900, Byungchul Park wrote:
> On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
> > > > >  void crossrelease_hist_end(enum context_t c)
> > > > >  {
> > > > > - if (current->xhlocks)
> > > > > - current->xhlock_idx = current->xhlock_idx_hist[c];
> > > > > + struct task_struct *cur = current;
> > > > > +
> > > > > + if (cur->xhlocks) {
> > > > > + unsigned int idx = cur->xhlock_idx_hist[c];
> > > > > + struct hist_lock *h = (idx);
> > > > > +
> > > > > + cur->xhlock_idx = idx;
> > > > > +
> > > > > + /* Check if the ring was overwritten. */
> > > > > + if (h->hist_id != cur->hist_id_save[c])
> > > > 
> > > > Could we use:
> > > > 
> > > > if (h->hist_id != idx)
> > > 
> > > No, we cannot.
> > > 
> > 
> > Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> > are increased at the same place(in add_xhlock()), right?
> 
> Right.
> 
> > And, yes, xhlock_idx will get decreased when we do ring-buffer
> 
> This is why we should keep both of them.
> 
> > unwinding, but that's OK, because we need to throw away those recently
> > added items.
> > 
> > And xhlock_idx always points to the most recently added valid item,
> 
> No, it's not true in case that the ring buffer was wrapped like:
> 
>   
> wrapped > 
>  ^
>  xhlock_idx points here after unwinding,
>  and it's not a valid one.
> 
>   where p represents an acquisition in process context,
>   i represents an acquisition in irq context.
> 

Yeah, but we can detect this with comparison between the
hist_lock::hist_id and the task_struct::xhlock_idx in
commit_xhlocks()(see my patch), no?

Regards,
Boqun

> > right?  Any other item's idx must "before()" the most recently added
> > one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?
> 
> Both of two answers are _no_.
> 
> > Maybe I'm missing something subtle, but could you show me an example,
> > that could end up being a problem if we use xhlock_idx as the hist_id?
> 
> See the example above. We cannot detect whether it was wrapped or not using
> xhlock_idx.
> 
> > 
> > > hist_id is a kind of timestamp and used to detect overwriting
> > > data into places of same indexes of the ring buffer. And idx is
> > > just an index. :) IOW, they mean different things.
> > > 
> > > > 
> > > > here, and
> > > > 
> > > > > + invalidate_xhlock(h);
> > > > > + }
> > > > >  }
> > > > >
> > > > >  static int cross_lock(struct lockdep_map *lock)
> > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > *hlock)
> > > > >   * Check if the xhlock is valid, which would be false if,
> > > > >   *
> > > > >   *1. Has not used after initializaion yet.
> > > > > + *2. Got invalidated.
> > > > >   *
> > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > >   */
> > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > >
> > > > >   /* Initialize hist_lock's members */
> > > > >   xhlock->hlock = *hlock;
> > > > > + xhlock->hist_id = current->hist_id++;
> > 
> > Besides, is this code correct? Does this just make xhlock->hist_id
> > one-less-than the curr->hist_id, which cause the invalidation every time
> > you do ring buffer unwinding?
> 
> Right. "save = hist_id++" should be "save = ++hist_id". Could you fix it?
> 
> Thank you,
> Byungchul
> 


signature.asc
Description: PGP signature

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> So basically, I'm suggesting do this on top of your patch, there is also
> a fix in commit_xhlocks(), which I think you should swap the parameters
> in before(...), no matter using task_struct::hist_id or using
> task_struct::xhlock_idx as the timestamp.
> 
> Hope this could make my point more clear, and if I do miss something,
> please point it out, thanks ;-)

I think I fully explained why we cannot use xhlock_idx as the timestamp
in another reply. Please let me know if it's not enough. :)

Thank you,
Byungchul

> Regards,
> Boqun
> >8
> 
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 074872f016f8..886ba79bfc38 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -854,9 +854,6 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 699fbeab1920..04c6c8d68e18 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum xhlock_context_t c)
> @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
>   cur->xhlock_idx = idx;
>  
>   /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> + if (h->hist_id != idx)
>   invalidate_xhlock(h);
>   }
>  }
> @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> - xhlock->hist_id = current->hist_id++;
> + xhlock->hist_id = idx;
>  
>   xhlock->trace.nr_entries = 0;
>   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>   unsigned int cur = current->xhlock_idx;
> - unsigned int prev_hist_id = xhlock(cur).hist_id;
> + unsigned int prev_hist_id = cur + 1;
>   unsigned int i;
>  
>   if (!graph_lock())
> @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>* hist_id than the following one, which is impossible
>* otherwise.
>*/
> - if (unlikely(before(xhlock->hist_id, prev_hist_id)))
> + if (unlikely(before(prev_hist_id, xhlock->hist_id)))
>   break;
>  
>   prev_hist_id = xhlock->hist_id;
> @@ -5120,12 +5118,9 @@ void lockdep_init_task(struct task_struct *task)
>   int i;
>  
>   task->xhlock_idx = UINT_MAX;
> - task->hist_id = 0;
>  
> - for (i = 0; i < XHLOCK_NR; i++) {
> + for (i = 0; i < XHLOCK_NR; i++)
>   task->xhlock_idx_hist[i] = UINT_MAX;
> - task->hist_id_save[i] = 0;
> - }
>  
>   task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
>   GFP_KERNEL);

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> So basically, I'm suggesting do this on top of your patch, there is also
> a fix in commit_xhlocks(), which I think you should swap the parameters
> in before(...), no matter using task_struct::hist_id or using
> task_struct::xhlock_idx as the timestamp.
> 
> Hope this could make my point more clear, and if I do miss something,
> please point it out, thanks ;-)

I think I fully explained why we cannot use xhlock_idx as the timestamp
in another reply. Please let me know if it's not enough. :)

Thank you,
Byungchul

> Regards,
> Boqun
> >8
> 
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 074872f016f8..886ba79bfc38 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -854,9 +854,6 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 699fbeab1920..04c6c8d68e18 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum xhlock_context_t c)
> @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
>   cur->xhlock_idx = idx;
>  
>   /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> + if (h->hist_id != idx)
>   invalidate_xhlock(h);
>   }
>  }
> @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> - xhlock->hist_id = current->hist_id++;
> + xhlock->hist_id = idx;
>  
>   xhlock->trace.nr_entries = 0;
>   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, 
> struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>   unsigned int cur = current->xhlock_idx;
> - unsigned int prev_hist_id = xhlock(cur).hist_id;
> + unsigned int prev_hist_id = cur + 1;
>   unsigned int i;
>  
>   if (!graph_lock())
> @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>* hist_id than the following one, which is impossible
>* otherwise.
>*/
> - if (unlikely(before(xhlock->hist_id, prev_hist_id)))
> + if (unlikely(before(prev_hist_id, xhlock->hist_id)))
>   break;
>  
>   prev_hist_id = xhlock->hist_id;
> @@ -5120,12 +5118,9 @@ void lockdep_init_task(struct task_struct *task)
>   int i;
>  
>   task->xhlock_idx = UINT_MAX;
> - task->hist_id = 0;
>  
> - for (i = 0; i < XHLOCK_NR; i++) {
> + for (i = 0; i < XHLOCK_NR; i++)
>   task->xhlock_idx_hist[i] = UINT_MAX;
> - task->hist_id_save[i] = 0;
> - }
>  
>   task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
>   GFP_KERNEL);

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
> > > >  void crossrelease_hist_end(enum context_t c)
> > > >  {
> > > > -   if (current->xhlocks)
> > > > -   current->xhlock_idx = current->xhlock_idx_hist[c];
> > > > +   struct task_struct *cur = current;
> > > > +
> > > > +   if (cur->xhlocks) {
> > > > +   unsigned int idx = cur->xhlock_idx_hist[c];
> > > > +   struct hist_lock *h = (idx);
> > > > +
> > > > +   cur->xhlock_idx = idx;
> > > > +
> > > > +   /* Check if the ring was overwritten. */
> > > > +   if (h->hist_id != cur->hist_id_save[c])
> > > 
> > > Could we use:
> > > 
> > >   if (h->hist_id != idx)
> > 
> > No, we cannot.
> > 
> 
> Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> are increased at the same place(in add_xhlock()), right?

Right.

> And, yes, xhlock_idx will get decreased when we do ring-buffer

This is why we should keep both of them.

> unwinding, but that's OK, because we need to throw away those recently
> added items.
> 
> And xhlock_idx always points to the most recently added valid item,

No, it's not true in case that the ring buffer was wrapped like:

  
wrapped > 
 ^
 xhlock_idx points here after unwinding,
 and it's not a valid one.

  where p represents an acquisition in process context,
  i represents an acquisition in irq context.

> right?  Any other item's idx must "before()" the most recently added
> one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?

Both of two answers are _no_.

> Maybe I'm missing something subtle, but could you show me an example,
> that could end up being a problem if we use xhlock_idx as the hist_id?

See the example above. We cannot detect whether it was wrapped or not using
xhlock_idx.

> 
> > hist_id is a kind of timestamp and used to detect overwriting
> > data into places of same indexes of the ring buffer. And idx is
> > just an index. :) IOW, they mean different things.
> > 
> > > 
> > > here, and
> > > 
> > > > +   invalidate_xhlock(h);
> > > > +   }
> > > >  }
> > > >
> > > >  static int cross_lock(struct lockdep_map *lock)
> > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > *hlock)
> > > >   * Check if the xhlock is valid, which would be false if,
> > > >   *
> > > >   *1. Has not used after initializaion yet.
> > > > + *2. Got invalidated.
> > > >   *
> > > >   * Remind hist_lock is implemented as a ring buffer.
> > > >   */
> > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > >
> > > > /* Initialize hist_lock's members */
> > > > xhlock->hlock = *hlock;
> > > > +   xhlock->hist_id = current->hist_id++;
> 
> Besides, is this code correct? Does this just make xhlock->hist_id
> one-less-than the curr->hist_id, which cause the invalidation every time
> you do ring buffer unwinding?

Right. "save = hist_id++" should be "save = ++hist_id". Could you fix it?

Thank you,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
> > > >  void crossrelease_hist_end(enum context_t c)
> > > >  {
> > > > -   if (current->xhlocks)
> > > > -   current->xhlock_idx = current->xhlock_idx_hist[c];
> > > > +   struct task_struct *cur = current;
> > > > +
> > > > +   if (cur->xhlocks) {
> > > > +   unsigned int idx = cur->xhlock_idx_hist[c];
> > > > +   struct hist_lock *h = (idx);
> > > > +
> > > > +   cur->xhlock_idx = idx;
> > > > +
> > > > +   /* Check if the ring was overwritten. */
> > > > +   if (h->hist_id != cur->hist_id_save[c])
> > > 
> > > Could we use:
> > > 
> > >   if (h->hist_id != idx)
> > 
> > No, we cannot.
> > 
> 
> Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> are increased at the same place(in add_xhlock()), right?

Right.

> And, yes, xhlock_idx will get decreased when we do ring-buffer

This is why we should keep both of them.

> unwinding, but that's OK, because we need to throw away those recently
> added items.
> 
> And xhlock_idx always points to the most recently added valid item,

No, it's not true in case that the ring buffer was wrapped like:

  
wrapped > 
 ^
 xhlock_idx points here after unwinding,
 and it's not a valid one.

  where p represents an acquisition in process context,
  i represents an acquisition in irq context.

> right?  Any other item's idx must "before()" the most recently added
> one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?

Both of two answers are _no_.

> Maybe I'm missing something subtle, but could you show me an example,
> that could end up being a problem if we use xhlock_idx as the hist_id?

See the example above. We cannot detect whether it was wrapped or not using
xhlock_idx.

> 
> > hist_id is a kind of timestamp and used to detect overwriting
> > data into places of same indexes of the ring buffer. And idx is
> > just an index. :) IOW, they mean different things.
> > 
> > > 
> > > here, and
> > > 
> > > > +   invalidate_xhlock(h);
> > > > +   }
> > > >  }
> > > >
> > > >  static int cross_lock(struct lockdep_map *lock)
> > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > *hlock)
> > > >   * Check if the xhlock is valid, which would be false if,
> > > >   *
> > > >   *1. Has not used after initializaion yet.
> > > > + *2. Got invalidated.
> > > >   *
> > > >   * Remind hist_lock is implemented as a ring buffer.
> > > >   */
> > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > >
> > > > /* Initialize hist_lock's members */
> > > > xhlock->hlock = *hlock;
> > > > +   xhlock->hist_id = current->hist_id++;
> 
> Besides, is this code correct? Does this just make xhlock->hist_id
> one-less-than the curr->hist_id, which cause the invalidation every time
> you do ring buffer unwinding?

Right. "save = hist_id++" should be "save = ++hist_id". Could you fix it?

Thank you,
Byungchul

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
[...]
> > > > +   /* Check if the ring was overwritten. */
> > > > +   if (h->hist_id != cur->hist_id_save[c])
> > > 
> > > Could we use:
> > > 
> > >   if (h->hist_id != idx)
> > 
> > No, we cannot.
> > 
> 
> Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> are increased at the same place(in add_xhlock()), right?
> 
> And, yes, xhlock_idx will get decreased when we do ring-buffer
> unwinding, but that's OK, because we need to throw away those recently
> added items.
> 
> And xhlock_idx always points to the most recently added valid item,
> right?  Any other item's idx must "before()" the most recently added
> one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?
> 
> Maybe I'm missing something subtle, but could you show me an example,
> that could end up being a problem if we use xhlock_idx as the hist_id?
> 
> > hist_id is a kind of timestamp and used to detect overwriting
> > data into places of same indexes of the ring buffer. And idx is
> > just an index. :) IOW, they mean different things.
> > 
> > > 
> > > here, and
> > > 
> > > > +   invalidate_xhlock(h);
> > > > +   }
> > > >  }
> > > >
> > > >  static int cross_lock(struct lockdep_map *lock)
> > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > *hlock)
> > > >   * Check if the xhlock is valid, which would be false if,
> > > >   *
> > > >   *1. Has not used after initializaion yet.
> > > > + *2. Got invalidated.
> > > >   *
> > > >   * Remind hist_lock is implemented as a ring buffer.
> > > >   */
> > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > >
> > > > /* Initialize hist_lock's members */
> > > > xhlock->hlock = *hlock;
> > > > +   xhlock->hist_id = current->hist_id++;
> 
> Besides, is this code correct? Does this just make xhlock->hist_id
> one-less-than the curr->hist_id, which cause the invalidation every time
> you do ring buffer unwinding?
> 
> Regards,
> Boqun
> 

So basically, I'm suggesting do this on top of your patch, there is also
a fix in commit_xhlocks(), which I think you should swap the parameters
in before(...), no matter using task_struct::hist_id or using
task_struct::xhlock_idx as the timestamp.

Hope this could make my point more clear, and if I do miss something,
please point it out, thanks ;-)

Regards,
Boqun
>8

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 074872f016f8..886ba79bfc38 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -854,9 +854,6 @@ struct task_struct {
unsigned int xhlock_idx;
/* For restoring at history boundaries */
unsigned int xhlock_idx_hist[XHLOCK_NR];
-   unsigned int hist_id;
-   /* For overwrite check at each context exit */
-   unsigned int hist_id_save[XHLOCK_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 699fbeab1920..04c6c8d68e18 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
 {
struct task_struct *cur = current;
 
-   if (cur->xhlocks) {
+   if (cur->xhlocks)
cur->xhlock_idx_hist[c] = cur->xhlock_idx;
-   cur->hist_id_save[c] = cur->hist_id;
-   }
 }
 
 void crossrelease_hist_end(enum xhlock_context_t c)
@@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
cur->xhlock_idx = idx;
 
/* Check if the ring was overwritten. */
-   if (h->hist_id != cur->hist_id_save[c])
+   if (h->hist_id != idx)
invalidate_xhlock(h);
}
 }
@@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
 
/* Initialize hist_lock's members */
xhlock->hlock = *hlock;
-   xhlock->hist_id = current->hist_id++;
+   xhlock->hist_id = idx;
 
xhlock->trace.nr_entries = 0;
xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct 
hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
unsigned int cur = current->xhlock_idx;
-   unsigned int prev_hist_id = xhlock(cur).hist_id;
+   unsigned int prev_hist_id = cur + 1;
unsigned int i;
 
if (!graph_lock())
@@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
 * hist_id than the following one, which is impossible
 * otherwise.
 */
-   if (unlikely(before(xhlock->hist_id, prev_hist_id)))
+   if (unlikely(before(prev_hist_id, xhlock->hist_id)))
break;
 
prev_hist_id = 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
[...]
> > > > +   /* Check if the ring was overwritten. */
> > > > +   if (h->hist_id != cur->hist_id_save[c])
> > > 
> > > Could we use:
> > > 
> > >   if (h->hist_id != idx)
> > 
> > No, we cannot.
> > 
> 
> Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> are increased at the same place(in add_xhlock()), right?
> 
> And, yes, xhlock_idx will get decreased when we do ring-buffer
> unwinding, but that's OK, because we need to throw away those recently
> added items.
> 
> And xhlock_idx always points to the most recently added valid item,
> right?  Any other item's idx must "before()" the most recently added
> one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?
> 
> Maybe I'm missing something subtle, but could you show me an example,
> that could end up being a problem if we use xhlock_idx as the hist_id?
> 
> > hist_id is a kind of timestamp and used to detect overwriting
> > data into places of same indexes of the ring buffer. And idx is
> > just an index. :) IOW, they mean different things.
> > 
> > > 
> > > here, and
> > > 
> > > > +   invalidate_xhlock(h);
> > > > +   }
> > > >  }
> > > >
> > > >  static int cross_lock(struct lockdep_map *lock)
> > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > *hlock)
> > > >   * Check if the xhlock is valid, which would be false if,
> > > >   *
> > > >   *1. Has not used after initializaion yet.
> > > > + *2. Got invalidated.
> > > >   *
> > > >   * Remind hist_lock is implemented as a ring buffer.
> > > >   */
> > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > >
> > > > /* Initialize hist_lock's members */
> > > > xhlock->hlock = *hlock;
> > > > +   xhlock->hist_id = current->hist_id++;
> 
> Besides, is this code correct? Does this just make xhlock->hist_id
> one-less-than the curr->hist_id, which cause the invalidation every time
> you do ring buffer unwinding?
> 
> Regards,
> Boqun
> 

So basically, I'm suggesting do this on top of your patch, there is also
a fix in commit_xhlocks(), which I think you should swap the parameters
in before(...), no matter using task_struct::hist_id or using
task_struct::xhlock_idx as the timestamp.

Hope this could make my point more clear, and if I do miss something,
please point it out, thanks ;-)

Regards,
Boqun
>8

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 074872f016f8..886ba79bfc38 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -854,9 +854,6 @@ struct task_struct {
unsigned int xhlock_idx;
/* For restoring at history boundaries */
unsigned int xhlock_idx_hist[XHLOCK_NR];
-   unsigned int hist_id;
-   /* For overwrite check at each context exit */
-   unsigned int hist_id_save[XHLOCK_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 699fbeab1920..04c6c8d68e18 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
 {
struct task_struct *cur = current;
 
-   if (cur->xhlocks) {
+   if (cur->xhlocks)
cur->xhlock_idx_hist[c] = cur->xhlock_idx;
-   cur->hist_id_save[c] = cur->hist_id;
-   }
 }
 
 void crossrelease_hist_end(enum xhlock_context_t c)
@@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
cur->xhlock_idx = idx;
 
/* Check if the ring was overwritten. */
-   if (h->hist_id != cur->hist_id_save[c])
+   if (h->hist_id != idx)
invalidate_xhlock(h);
}
 }
@@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
 
/* Initialize hist_lock's members */
xhlock->hlock = *hlock;
-   xhlock->hist_id = current->hist_id++;
+   xhlock->hist_id = idx;
 
xhlock->trace.nr_entries = 0;
xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct 
hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
unsigned int cur = current->xhlock_idx;
-   unsigned int prev_hist_id = xhlock(cur).hist_id;
+   unsigned int prev_hist_id = cur + 1;
unsigned int i;
 
if (!graph_lock())
@@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
 * hist_id than the following one, which is impossible
 * otherwise.
 */
-   if (unlikely(before(xhlock->hist_id, prev_hist_id)))
+   if (unlikely(before(prev_hist_id, xhlock->hist_id)))
break;
 
prev_hist_id = 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Thu, Aug 10, 2017 at 09:11:32PM +0900, Byungchul Park wrote:
> > -Original Message-
> > From: Boqun Feng [mailto:boqun.f...@gmail.com]
> > Sent: Thursday, August 10, 2017 8:59 PM
> > To: Byungchul Park
> > Cc: pet...@infradead.org; mi...@kernel.org; t...@linutronix.de;
> > wal...@google.com; kir...@shutemov.name; linux-kernel@vger.kernel.org;
> > linux...@kvack.org; a...@linux-foundation.org; wi...@infradead.org;
> > npig...@gmail.com; kernel-t...@lge.com
> > Subject: Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring
> > buffer overwrite
> > 
> > On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> > > The ring buffer can be overwritten by hardirq/softirq/work contexts.
> > > That cases must be considered on rollback or commit. For example,
> > >
> > >   |<-- hist_lock ring buffer size ->|
> > >   iii
> > > wrapped > iii
> > >
> > >   where 'p' represents an acquisition in process context,
> > >   'i' represents an acquisition in irq context.
> > >
> > > On irq exit, crossrelease tries to rollback idx to original position,
> > > but it should not because the entry already has been invalid by
> > > overwriting 'i'. Avoid rollback or commit for entries overwritten.
> > >
> > > Signed-off-by: Byungchul Park <byungchul.p...@lge.com>
> > > ---
> > >  include/linux/lockdep.h  | 20 +++
> > >  include/linux/sched.h|  3 +++
> > >  kernel/locking/lockdep.c | 52
> > +++-
> > >  3 files changed, 70 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > > index 0c8a1b8..48c244c 100644
> > > --- a/include/linux/lockdep.h
> > > +++ b/include/linux/lockdep.h
> > > @@ -284,6 +284,26 @@ struct held_lock {
> > >   */
> > >  struct hist_lock {
> > >   /*
> > > +  * Id for each entry in the ring buffer. This is used to
> > > +  * decide whether the ring buffer was overwritten or not.
> > > +  *
> > > +  * For example,
> > > +  *
> > > +  *   |<--- hist_lock ring buffer size --->|
> > > +  *   pi
> > > +  * wrapped > iii...
> > > +  *
> > > +  *   where 'p' represents an acquisition in process
> > > +  *   context, 'i' represents an acquisition in irq
> > > +  *   context.
> > > +  *
> > > +  * In this example, the ring buffer was overwritten by
> > > +  * acquisitions in irq context, that should be detected on
> > > +  * rollback or commit.
> > > +  */
> > > + unsigned int hist_id;
> > > +
> > > + /*
> > >* Seperate stack_trace data. This will be used at commit step.
> > >*/
> > >   struct stack_trace  trace;
> > > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > > index 5becef5..373466b 100644
> > > --- a/include/linux/sched.h
> > > +++ b/include/linux/sched.h
> > > @@ -855,6 +855,9 @@ struct task_struct {
> > >   unsigned int xhlock_idx;
> > >   /* For restoring at history boundaries */
> > >   unsigned int xhlock_idx_hist[CONTEXT_NR];
> > > + unsigned int hist_id;
> > > + /* For overwrite check at each context exit */
> > > + unsigned int hist_id_save[CONTEXT_NR];
> > >  #endif
> > >
> > >  #ifdef CONFIG_UBSAN
> > > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > > index afd6e64..5168dac 100644
> > > --- a/kernel/locking/lockdep.c
> > > +++ b/kernel/locking/lockdep.c
> > > @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file,
> > const int line, const char *s)
> > >  static atomic_t cross_gen_id; /* Can be wrapped */
> > >
> > >  /*
> > > + * Make an entry of the ring buffer invalid.
> > > + */
> > > +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> > > +{
> > > + /*
> > > +  * Normally, xhlock->hlock.instance must be !NULL.
> > > +  */
> > > + xhlock->hlock.instance = NULL;
> > > +}
> > > +
> > > +/*
> > >   * Lock history stacks; we have 3 nested l

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Thu, Aug 10, 2017 at 09:11:32PM +0900, Byungchul Park wrote:
> > -Original Message-
> > From: Boqun Feng [mailto:boqun.f...@gmail.com]
> > Sent: Thursday, August 10, 2017 8:59 PM
> > To: Byungchul Park
> > Cc: pet...@infradead.org; mi...@kernel.org; t...@linutronix.de;
> > wal...@google.com; kir...@shutemov.name; linux-kernel@vger.kernel.org;
> > linux...@kvack.org; a...@linux-foundation.org; wi...@infradead.org;
> > npig...@gmail.com; kernel-t...@lge.com
> > Subject: Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring
> > buffer overwrite
> > 
> > On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> > > The ring buffer can be overwritten by hardirq/softirq/work contexts.
> > > That cases must be considered on rollback or commit. For example,
> > >
> > >   |<-- hist_lock ring buffer size ->|
> > >   iii
> > > wrapped > iii
> > >
> > >   where 'p' represents an acquisition in process context,
> > >   'i' represents an acquisition in irq context.
> > >
> > > On irq exit, crossrelease tries to rollback idx to original position,
> > > but it should not because the entry already has been invalid by
> > > overwriting 'i'. Avoid rollback or commit for entries overwritten.
> > >
> > > Signed-off-by: Byungchul Park 
> > > ---
> > >  include/linux/lockdep.h  | 20 +++
> > >  include/linux/sched.h|  3 +++
> > >  kernel/locking/lockdep.c | 52
> > +++-
> > >  3 files changed, 70 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > > index 0c8a1b8..48c244c 100644
> > > --- a/include/linux/lockdep.h
> > > +++ b/include/linux/lockdep.h
> > > @@ -284,6 +284,26 @@ struct held_lock {
> > >   */
> > >  struct hist_lock {
> > >   /*
> > > +  * Id for each entry in the ring buffer. This is used to
> > > +  * decide whether the ring buffer was overwritten or not.
> > > +  *
> > > +  * For example,
> > > +  *
> > > +  *   |<--- hist_lock ring buffer size --->|
> > > +  *   pi
> > > +  * wrapped > iii...
> > > +  *
> > > +  *   where 'p' represents an acquisition in process
> > > +  *   context, 'i' represents an acquisition in irq
> > > +  *   context.
> > > +  *
> > > +  * In this example, the ring buffer was overwritten by
> > > +  * acquisitions in irq context, that should be detected on
> > > +  * rollback or commit.
> > > +  */
> > > + unsigned int hist_id;
> > > +
> > > + /*
> > >* Seperate stack_trace data. This will be used at commit step.
> > >*/
> > >   struct stack_trace  trace;
> > > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > > index 5becef5..373466b 100644
> > > --- a/include/linux/sched.h
> > > +++ b/include/linux/sched.h
> > > @@ -855,6 +855,9 @@ struct task_struct {
> > >   unsigned int xhlock_idx;
> > >   /* For restoring at history boundaries */
> > >   unsigned int xhlock_idx_hist[CONTEXT_NR];
> > > + unsigned int hist_id;
> > > + /* For overwrite check at each context exit */
> > > + unsigned int hist_id_save[CONTEXT_NR];
> > >  #endif
> > >
> > >  #ifdef CONFIG_UBSAN
> > > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > > index afd6e64..5168dac 100644
> > > --- a/kernel/locking/lockdep.c
> > > +++ b/kernel/locking/lockdep.c
> > > @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file,
> > const int line, const char *s)
> > >  static atomic_t cross_gen_id; /* Can be wrapped */
> > >
> > >  /*
> > > + * Make an entry of the ring buffer invalid.
> > > + */
> > > +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> > > +{
> > > + /*
> > > +  * Normally, xhlock->hlock.instance must be !NULL.
> > > +  */
> > > + xhlock->hlock.instance = NULL;
> > > +}
> > > +
> > > +/*
> > >   * Lock history stacks; we have 3 nested lock history stacks:
> > >  

RE: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

> -Original Message-
> From: Boqun Feng [mailto:boqun.f...@gmail.com]
> Sent: Thursday, August 10, 2017 8:59 PM
> To: Byungchul Park
> Cc: pet...@infradead.org; mi...@kernel.org; t...@linutronix.de;
> wal...@google.com; kir...@shutemov.name; linux-kernel@vger.kernel.org;
> linux...@kvack.org; a...@linux-foundation.org; wi...@infradead.org;
> npig...@gmail.com; kernel-t...@lge.com
> Subject: Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring
> buffer overwrite
> 
> On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> > The ring buffer can be overwritten by hardirq/softirq/work contexts.
> > That cases must be considered on rollback or commit. For example,
> >
> >   |<-- hist_lock ring buffer size ->|
> >   iii
> > wrapped > iii
> >
> >   where 'p' represents an acquisition in process context,
> >   'i' represents an acquisition in irq context.
> >
> > On irq exit, crossrelease tries to rollback idx to original position,
> > but it should not because the entry already has been invalid by
> > overwriting 'i'. Avoid rollback or commit for entries overwritten.
> >
> > Signed-off-by: Byungchul Park <byungchul.p...@lge.com>
> > ---
> >  include/linux/lockdep.h  | 20 +++
> >  include/linux/sched.h|  3 +++
> >  kernel/locking/lockdep.c | 52
> +++-
> >  3 files changed, 70 insertions(+), 5 deletions(-)
> >
> > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > index 0c8a1b8..48c244c 100644
> > --- a/include/linux/lockdep.h
> > +++ b/include/linux/lockdep.h
> > @@ -284,6 +284,26 @@ struct held_lock {
> >   */
> >  struct hist_lock {
> > /*
> > +* Id for each entry in the ring buffer. This is used to
> > +* decide whether the ring buffer was overwritten or not.
> > +*
> > +* For example,
> > +*
> > +*   |<--- hist_lock ring buffer size --->|
> > +*   pi
> > +* wrapped > iii...
> > +*
> > +*   where 'p' represents an acquisition in process
> > +*   context, 'i' represents an acquisition in irq
> > +*   context.
> > +*
> > +* In this example, the ring buffer was overwritten by
> > +* acquisitions in irq context, that should be detected on
> > +* rollback or commit.
> > +*/
> > +   unsigned int hist_id;
> > +
> > +   /*
> >  * Seperate stack_trace data. This will be used at commit step.
> >  */
> > struct stack_trace  trace;
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 5becef5..373466b 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -855,6 +855,9 @@ struct task_struct {
> > unsigned int xhlock_idx;
> > /* For restoring at history boundaries */
> > unsigned int xhlock_idx_hist[CONTEXT_NR];
> > +   unsigned int hist_id;
> > +   /* For overwrite check at each context exit */
> > +   unsigned int hist_id_save[CONTEXT_NR];
> >  #endif
> >
> >  #ifdef CONFIG_UBSAN
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index afd6e64..5168dac 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file,
> const int line, const char *s)
> >  static atomic_t cross_gen_id; /* Can be wrapped */
> >
> >  /*
> > + * Make an entry of the ring buffer invalid.
> > + */
> > +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> > +{
> > +   /*
> > +* Normally, xhlock->hlock.instance must be !NULL.
> > +*/
> > +   xhlock->hlock.instance = NULL;
> > +}
> > +
> > +/*
> >   * Lock history stacks; we have 3 nested lock history stacks:
> >   *
> >   *   Hard IRQ
> > @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file,
> const int line, const char *s)
> >   */
> >  void crossrelease_hist_start(enum context_t c)
> >  {
> > -   if (current->xhlocks)
> > -   current->xhlock_idx_hist[c] = current->xhlock_idx;
> > +   struct task_struct *cur = current;
> > +
> > +   if (cur->xhlocks) {
> > +   cur->xh

RE: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

> -Original Message-
> From: Boqun Feng [mailto:boqun.f...@gmail.com]
> Sent: Thursday, August 10, 2017 8:59 PM
> To: Byungchul Park
> Cc: pet...@infradead.org; mi...@kernel.org; t...@linutronix.de;
> wal...@google.com; kir...@shutemov.name; linux-kernel@vger.kernel.org;
> linux...@kvack.org; a...@linux-foundation.org; wi...@infradead.org;
> npig...@gmail.com; kernel-t...@lge.com
> Subject: Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring
> buffer overwrite
> 
> On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> > The ring buffer can be overwritten by hardirq/softirq/work contexts.
> > That cases must be considered on rollback or commit. For example,
> >
> >   |<-- hist_lock ring buffer size ->|
> >   iii
> > wrapped > iii
> >
> >   where 'p' represents an acquisition in process context,
> >   'i' represents an acquisition in irq context.
> >
> > On irq exit, crossrelease tries to rollback idx to original position,
> > but it should not because the entry already has been invalid by
> > overwriting 'i'. Avoid rollback or commit for entries overwritten.
> >
> > Signed-off-by: Byungchul Park 
> > ---
> >  include/linux/lockdep.h  | 20 +++
> >  include/linux/sched.h|  3 +++
> >  kernel/locking/lockdep.c | 52
> +++-
> >  3 files changed, 70 insertions(+), 5 deletions(-)
> >
> > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > index 0c8a1b8..48c244c 100644
> > --- a/include/linux/lockdep.h
> > +++ b/include/linux/lockdep.h
> > @@ -284,6 +284,26 @@ struct held_lock {
> >   */
> >  struct hist_lock {
> > /*
> > +* Id for each entry in the ring buffer. This is used to
> > +* decide whether the ring buffer was overwritten or not.
> > +*
> > +* For example,
> > +*
> > +*   |<--- hist_lock ring buffer size --->|
> > +*   pi
> > +* wrapped > iii...
> > +*
> > +*   where 'p' represents an acquisition in process
> > +*   context, 'i' represents an acquisition in irq
> > +*   context.
> > +*
> > +* In this example, the ring buffer was overwritten by
> > +* acquisitions in irq context, that should be detected on
> > +* rollback or commit.
> > +*/
> > +   unsigned int hist_id;
> > +
> > +   /*
> >  * Seperate stack_trace data. This will be used at commit step.
> >  */
> > struct stack_trace  trace;
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 5becef5..373466b 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -855,6 +855,9 @@ struct task_struct {
> > unsigned int xhlock_idx;
> > /* For restoring at history boundaries */
> > unsigned int xhlock_idx_hist[CONTEXT_NR];
> > +   unsigned int hist_id;
> > +   /* For overwrite check at each context exit */
> > +   unsigned int hist_id_save[CONTEXT_NR];
> >  #endif
> >
> >  #ifdef CONFIG_UBSAN
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index afd6e64..5168dac 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file,
> const int line, const char *s)
> >  static atomic_t cross_gen_id; /* Can be wrapped */
> >
> >  /*
> > + * Make an entry of the ring buffer invalid.
> > + */
> > +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> > +{
> > +   /*
> > +* Normally, xhlock->hlock.instance must be !NULL.
> > +*/
> > +   xhlock->hlock.instance = NULL;
> > +}
> > +
> > +/*
> >   * Lock history stacks; we have 3 nested lock history stacks:
> >   *
> >   *   Hard IRQ
> > @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file,
> const int line, const char *s)
> >   */
> >  void crossrelease_hist_start(enum context_t c)
> >  {
> > -   if (current->xhlocks)
> > -   current->xhlock_idx_hist[c] = current->xhlock_idx;
> > +   struct task_struct *cur = current;
> > +
> > +   if (cur->xhlocks) {
> > +   cur->xhlock_idx_hist[c] = cur->xhlock

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> The ring buffer can be overwritten by hardirq/softirq/work contexts.
> That cases must be considered on rollback or commit. For example,
> 
>   |<-- hist_lock ring buffer size ->|
>   iii
> wrapped > iii
> 
>   where 'p' represents an acquisition in process context,
>   'i' represents an acquisition in irq context.
> 
> On irq exit, crossrelease tries to rollback idx to original position,
> but it should not because the entry already has been invalid by
> overwriting 'i'. Avoid rollback or commit for entries overwritten.
> 
> Signed-off-by: Byungchul Park 
> ---
>  include/linux/lockdep.h  | 20 +++
>  include/linux/sched.h|  3 +++
>  kernel/locking/lockdep.c | 52 
> +++-
>  3 files changed, 70 insertions(+), 5 deletions(-)
> 
> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index 0c8a1b8..48c244c 100644
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,6 +284,26 @@ struct held_lock {
>   */
>  struct hist_lock {
>   /*
> +  * Id for each entry in the ring buffer. This is used to
> +  * decide whether the ring buffer was overwritten or not.
> +  *
> +  * For example,
> +  *
> +  *   |<--- hist_lock ring buffer size --->|
> +  *   pi
> +  * wrapped > iii...
> +  *
> +  *   where 'p' represents an acquisition in process
> +  *   context, 'i' represents an acquisition in irq
> +  *   context.
> +  *
> +  * In this example, the ring buffer was overwritten by
> +  * acquisitions in irq context, that should be detected on
> +  * rollback or commit.
> +  */
> + unsigned int hist_id;
> +
> + /*
>* Seperate stack_trace data. This will be used at commit step.
>*/
>   struct stack_trace  trace;
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 5becef5..373466b 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,6 +855,9 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[CONTEXT_NR];
> + unsigned int hist_id;
> + /* For overwrite check at each context exit */
> + unsigned int hist_id_save[CONTEXT_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index afd6e64..5168dac 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file, const 
> int line, const char *s)
>  static atomic_t cross_gen_id; /* Can be wrapped */
>  
>  /*
> + * Make an entry of the ring buffer invalid.
> + */
> +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> +{
> + /*
> +  * Normally, xhlock->hlock.instance must be !NULL.
> +  */
> + xhlock->hlock.instance = NULL;
> +}
> +
> +/*
>   * Lock history stacks; we have 3 nested lock history stacks:
>   *
>   *   Hard IRQ
> @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const 
> int line, const char *s)
>   */
>  void crossrelease_hist_start(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx_hist[c] = current->xhlock_idx;
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> + cur->hist_id_save[c] = cur->hist_id;
> + }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx = current->xhlock_idx_hist[c];
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + unsigned int idx = cur->xhlock_idx_hist[c];
> + struct hist_lock *h = (idx);
> +
> + cur->xhlock_idx = idx;
> +
> + /* Check if the ring was overwritten. */
> + if (h->hist_id != cur->hist_id_save[c])

Could we use:

if (h->hist_id != idx)

here, and

> + invalidate_xhlock(h);
> + }
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
>   * Check if the xhlock is valid, which would be false if,
>   *
>   *1. Has not used after initializaion yet.
> + *2. Got invalidated.
>   *
>   * Remind hist_lock is implemented as a ring buffer.
>   */
> @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> + xhlock->hist_id = current->hist_id++;

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Boqun Feng]

On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> The ring buffer can be overwritten by hardirq/softirq/work contexts.
> That cases must be considered on rollback or commit. For example,
> 
>   |<-- hist_lock ring buffer size ->|
>   iii
> wrapped > iii
> 
>   where 'p' represents an acquisition in process context,
>   'i' represents an acquisition in irq context.
> 
> On irq exit, crossrelease tries to rollback idx to original position,
> but it should not because the entry already has been invalid by
> overwriting 'i'. Avoid rollback or commit for entries overwritten.
> 
> Signed-off-by: Byungchul Park 
> ---
>  include/linux/lockdep.h  | 20 +++
>  include/linux/sched.h|  3 +++
>  kernel/locking/lockdep.c | 52 
> +++-
>  3 files changed, 70 insertions(+), 5 deletions(-)
> 
> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index 0c8a1b8..48c244c 100644
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,6 +284,26 @@ struct held_lock {
>   */
>  struct hist_lock {
>   /*
> +  * Id for each entry in the ring buffer. This is used to
> +  * decide whether the ring buffer was overwritten or not.
> +  *
> +  * For example,
> +  *
> +  *   |<--- hist_lock ring buffer size --->|
> +  *   pi
> +  * wrapped > iii...
> +  *
> +  *   where 'p' represents an acquisition in process
> +  *   context, 'i' represents an acquisition in irq
> +  *   context.
> +  *
> +  * In this example, the ring buffer was overwritten by
> +  * acquisitions in irq context, that should be detected on
> +  * rollback or commit.
> +  */
> + unsigned int hist_id;
> +
> + /*
>* Seperate stack_trace data. This will be used at commit step.
>*/
>   struct stack_trace  trace;
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 5becef5..373466b 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,6 +855,9 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[CONTEXT_NR];
> + unsigned int hist_id;
> + /* For overwrite check at each context exit */
> + unsigned int hist_id_save[CONTEXT_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index afd6e64..5168dac 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file, const 
> int line, const char *s)
>  static atomic_t cross_gen_id; /* Can be wrapped */
>  
>  /*
> + * Make an entry of the ring buffer invalid.
> + */
> +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> +{
> + /*
> +  * Normally, xhlock->hlock.instance must be !NULL.
> +  */
> + xhlock->hlock.instance = NULL;
> +}
> +
> +/*
>   * Lock history stacks; we have 3 nested lock history stacks:
>   *
>   *   Hard IRQ
> @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const 
> int line, const char *s)
>   */
>  void crossrelease_hist_start(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx_hist[c] = current->xhlock_idx;
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> + cur->hist_id_save[c] = cur->hist_id;
> + }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx = current->xhlock_idx_hist[c];
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + unsigned int idx = cur->xhlock_idx_hist[c];
> + struct hist_lock *h = (idx);
> +
> + cur->xhlock_idx = idx;
> +
> + /* Check if the ring was overwritten. */
> + if (h->hist_id != cur->hist_id_save[c])

Could we use:

if (h->hist_id != idx)

here, and

> + invalidate_xhlock(h);
> + }
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
>   * Check if the xhlock is valid, which would be false if,
>   *
>   *1. Has not used after initializaion yet.
> + *2. Got invalidated.
>   *
>   * Remind hist_lock is implemented as a ring buffer.
>   */
> @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> + xhlock->hist_id = current->hist_id++;

use:

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> 
> Hehe, _another_ scheme...
> 
> Yes I think this works.. but I had just sort of understood the last one.
> 
> How about I do this on top? That I think is a combination of what I
> proposed last and your single invalidate thing. Combined they solve the
> problem with the least amount of extra storage (a single int).
> 

I like your trying because it looks like making code simple, but there are
some cases the patch does not cover.

  pppwi
wrapped > i

  where,
  p: process
  w: work
  i: irq

In this case, your patch cannot detect overwriting 'w' with 'i'. What do
you think about it?

> ---
> Subject: lockdep: Simplify xhlock ring buffer invalidation
> From: Peter Zijlstra 
> Date: Wed Aug 9 15:31:27 CEST 2017
> 
> 
> Signed-off-by: Peter Zijlstra (Intel) 
> ---
>  include/linux/lockdep.h  |   20 ---
>  include/linux/sched.h|4 --
>  kernel/locking/lockdep.c |   82 
> ++-
>  3 files changed, 54 insertions(+), 52 deletions(-)
> 
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,26 +284,6 @@ struct held_lock {
>   */
>  struct hist_lock {
>   /*
> -  * Id for each entry in the ring buffer. This is used to
> -  * decide whether the ring buffer was overwritten or not.
> -  *
> -  * For example,
> -  *
> -  *   |<--- hist_lock ring buffer size --->|
> -  *   pi
> -  * wrapped > iii...
> -  *
> -  *   where 'p' represents an acquisition in process
> -  *   context, 'i' represents an acquisition in irq
> -  *   context.
> -  *
> -  * In this example, the ring buffer was overwritten by
> -  * acquisitions in irq context, that should be detected on
> -  * rollback or commit.
> -  */
> - unsigned int hist_id;
> -
> - /*
>* Seperate stack_trace data. This will be used at commit step.
>*/
>   struct stack_trace  trace;
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,9 +855,7 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
> + unsigned int xhlock_idx_max;
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
>   struct task_struct *cur = current;
> + unsigned int idx;
>  
> - if (cur->xhlocks) {
> - unsigned int idx = cur->xhlock_idx_hist[c];
> - struct hist_lock *h = (idx);
> -
> - cur->xhlock_idx = idx;
> -
> - /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> - invalidate_xhlock(h);
> - }
> + if (!cur->xhlocks)
> + return;
> +
> + idx = cur->xhlock_idx_hist[c];
> + cur->xhlock_idx = idx;
> +
> + /*
> +  * A bit of magic here.. this deals with rewinding the (cyclic) history
> +  * array further than its size. IOW. looses the complete history.
> +  *
> +  * We detect this by tracking the previous oldest entry we've (over)
> +  * written in @xhlock_idx_max, this means the next entry is the oldest
> +  * entry still in the buffer, ie. its tail.
> +  *
> +  * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
> +  * older than @xhlock_idx_max we know we've just wiped the entire
> +  * history.
> +  */
> + if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
> + return;
> +
> + /*
> +  * Now that we know the buffer is effectively empty, reset our state
> +  * such that it appears empty (without in fact clearing the entire
> +  * buffer).
> +  *
> +  * Pick @idx as the 'new' beginning, (re)set all save-points to not
> +  * rewind past it and reset the max. Then invalidate this idx such that
> +  * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
> +  * will return the _next_ entry, we'll not overwrite this invalid entry
> +  * until the entire buffer is full again.
> +  */
> + for (c = 0; c < 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> 
> Hehe, _another_ scheme...
> 
> Yes I think this works.. but I had just sort of understood the last one.
> 
> How about I do this on top? That I think is a combination of what I
> proposed last and your single invalidate thing. Combined they solve the
> problem with the least amount of extra storage (a single int).
> 

I like your trying because it looks like making code simple, but there are
some cases the patch does not cover.

  pppwi
wrapped > i

  where,
  p: process
  w: work
  i: irq

In this case, your patch cannot detect overwriting 'w' with 'i'. What do
you think about it?

> ---
> Subject: lockdep: Simplify xhlock ring buffer invalidation
> From: Peter Zijlstra 
> Date: Wed Aug 9 15:31:27 CEST 2017
> 
> 
> Signed-off-by: Peter Zijlstra (Intel) 
> ---
>  include/linux/lockdep.h  |   20 ---
>  include/linux/sched.h|4 --
>  kernel/locking/lockdep.c |   82 
> ++-
>  3 files changed, 54 insertions(+), 52 deletions(-)
> 
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,26 +284,6 @@ struct held_lock {
>   */
>  struct hist_lock {
>   /*
> -  * Id for each entry in the ring buffer. This is used to
> -  * decide whether the ring buffer was overwritten or not.
> -  *
> -  * For example,
> -  *
> -  *   |<--- hist_lock ring buffer size --->|
> -  *   pi
> -  * wrapped > iii...
> -  *
> -  *   where 'p' represents an acquisition in process
> -  *   context, 'i' represents an acquisition in irq
> -  *   context.
> -  *
> -  * In this example, the ring buffer was overwritten by
> -  * acquisitions in irq context, that should be detected on
> -  * rollback or commit.
> -  */
> - unsigned int hist_id;
> -
> - /*
>* Seperate stack_trace data. This will be used at commit step.
>*/
>   struct stack_trace  trace;
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,9 +855,7 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
> + unsigned int xhlock_idx_max;
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
>   struct task_struct *cur = current;
> + unsigned int idx;
>  
> - if (cur->xhlocks) {
> - unsigned int idx = cur->xhlock_idx_hist[c];
> - struct hist_lock *h = (idx);
> -
> - cur->xhlock_idx = idx;
> -
> - /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> - invalidate_xhlock(h);
> - }
> + if (!cur->xhlocks)
> + return;
> +
> + idx = cur->xhlock_idx_hist[c];
> + cur->xhlock_idx = idx;
> +
> + /*
> +  * A bit of magic here.. this deals with rewinding the (cyclic) history
> +  * array further than its size. IOW. looses the complete history.
> +  *
> +  * We detect this by tracking the previous oldest entry we've (over)
> +  * written in @xhlock_idx_max, this means the next entry is the oldest
> +  * entry still in the buffer, ie. its tail.
> +  *
> +  * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
> +  * older than @xhlock_idx_max we know we've just wiped the entire
> +  * history.
> +  */
> + if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
> + return;
> +
> + /*
> +  * Now that we know the buffer is effectively empty, reset our state
> +  * such that it appears empty (without in fact clearing the entire
> +  * buffer).
> +  *
> +  * Pick @idx as the 'new' beginning, (re)set all save-points to not
> +  * rewind past it and reset the max. Then invalidate this idx such that
> +  * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
> +  * will return the _next_ entry, we'll not overwrite this invalid entry
> +  * until the entire buffer is full again.
> +  */
> + for (c = 0; c < XHLOCK_NR; c++)
> + 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Peter Zijlstra]

On Thu, Aug 10, 2017 at 10:32:16AM +0900, Byungchul Park wrote:
> On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> > Hehe, _another_ scheme...
> > 
> > Yes I think this works.. but I had just sort of understood the last one.
> > 
> > How about I do this on top? That I think is a combination of what I
> > proposed last and your single invalidate thing. Combined they solve the
> > problem with the least amount of extra storage (a single int).
> 
> I'm sorry for saying that.. I'm not sure if this works well.

OK, I'll sit on the patch a little while, if you could share your
concerns then maybe I can improve the comments ;-)

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Peter Zijlstra]

On Thu, Aug 10, 2017 at 10:32:16AM +0900, Byungchul Park wrote:
> On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> > Hehe, _another_ scheme...
> > 
> > Yes I think this works.. but I had just sort of understood the last one.
> > 
> > How about I do this on top? That I think is a combination of what I
> > proposed last and your single invalidate thing. Combined they solve the
> > problem with the least amount of extra storage (a single int).
> 
> I'm sorry for saying that.. I'm not sure if this works well.

OK, I'll sit on the patch a little while, if you could share your
concerns then maybe I can improve the comments ;-)

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> Hehe, _another_ scheme...
> 
> Yes I think this works.. but I had just sort of understood the last one.
> 
> How about I do this on top? That I think is a combination of what I
> proposed last and your single invalidate thing. Combined they solve the
> problem with the least amount of extra storage (a single int).

I'm sorry for saying that.. I'm not sure if this works well.

> ---
> Subject: lockdep: Simplify xhlock ring buffer invalidation
> From: Peter Zijlstra 
> Date: Wed Aug 9 15:31:27 CEST 2017
> 
> 
> Signed-off-by: Peter Zijlstra (Intel) 
> ---
>  include/linux/lockdep.h  |   20 ---
>  include/linux/sched.h|4 --
>  kernel/locking/lockdep.c |   82 
> ++-
>  3 files changed, 54 insertions(+), 52 deletions(-)
> 
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,26 +284,6 @@ struct held_lock {
>   */
>  struct hist_lock {
>   /*
> -  * Id for each entry in the ring buffer. This is used to
> -  * decide whether the ring buffer was overwritten or not.
> -  *
> -  * For example,
> -  *
> -  *   |<--- hist_lock ring buffer size --->|
> -  *   pi
> -  * wrapped > iii...
> -  *
> -  *   where 'p' represents an acquisition in process
> -  *   context, 'i' represents an acquisition in irq
> -  *   context.
> -  *
> -  * In this example, the ring buffer was overwritten by
> -  * acquisitions in irq context, that should be detected on
> -  * rollback or commit.
> -  */
> - unsigned int hist_id;
> -
> - /*
>* Seperate stack_trace data. This will be used at commit step.
>*/
>   struct stack_trace  trace;
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,9 +855,7 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
> + unsigned int xhlock_idx_max;
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
>   struct task_struct *cur = current;
> + unsigned int idx;
>  
> - if (cur->xhlocks) {
> - unsigned int idx = cur->xhlock_idx_hist[c];
> - struct hist_lock *h = (idx);
> -
> - cur->xhlock_idx = idx;
> -
> - /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> - invalidate_xhlock(h);
> - }
> + if (!cur->xhlocks)
> + return;
> +
> + idx = cur->xhlock_idx_hist[c];
> + cur->xhlock_idx = idx;
> +
> + /*
> +  * A bit of magic here.. this deals with rewinding the (cyclic) history
> +  * array further than its size. IOW. looses the complete history.
> +  *
> +  * We detect this by tracking the previous oldest entry we've (over)
> +  * written in @xhlock_idx_max, this means the next entry is the oldest
> +  * entry still in the buffer, ie. its tail.
> +  *
> +  * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
> +  * older than @xhlock_idx_max we know we've just wiped the entire
> +  * history.
> +  */
> + if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
> + return;
> +
> + /*
> +  * Now that we know the buffer is effectively empty, reset our state
> +  * such that it appears empty (without in fact clearing the entire
> +  * buffer).
> +  *
> +  * Pick @idx as the 'new' beginning, (re)set all save-points to not
> +  * rewind past it and reset the max. Then invalidate this idx such that
> +  * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
> +  * will return the _next_ entry, we'll not overwrite this invalid entry
> +  * until the entire buffer is full again.
> +  */
> + for (c = 0; c < XHLOCK_NR; c++)
> + cur->xhlock_idx_hist[c] = idx;
> + cur->xhlock_idx_max = idx;
> + invalidate_xhlock((idx));
> +}
> +
> +static inline unsigned int xhlock_idx_inc(void)
> +{
> + struct task_struct *cur = current;
> + unsigned int idx = ++cur->xhlock_idx;
> +
> + /*
> +  * As per the requirement in 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> Hehe, _another_ scheme...
> 
> Yes I think this works.. but I had just sort of understood the last one.
> 
> How about I do this on top? That I think is a combination of what I
> proposed last and your single invalidate thing. Combined they solve the
> problem with the least amount of extra storage (a single int).

I'm sorry for saying that.. I'm not sure if this works well.

> ---
> Subject: lockdep: Simplify xhlock ring buffer invalidation
> From: Peter Zijlstra 
> Date: Wed Aug 9 15:31:27 CEST 2017
> 
> 
> Signed-off-by: Peter Zijlstra (Intel) 
> ---
>  include/linux/lockdep.h  |   20 ---
>  include/linux/sched.h|4 --
>  kernel/locking/lockdep.c |   82 
> ++-
>  3 files changed, 54 insertions(+), 52 deletions(-)
> 
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,26 +284,6 @@ struct held_lock {
>   */
>  struct hist_lock {
>   /*
> -  * Id for each entry in the ring buffer. This is used to
> -  * decide whether the ring buffer was overwritten or not.
> -  *
> -  * For example,
> -  *
> -  *   |<--- hist_lock ring buffer size --->|
> -  *   pi
> -  * wrapped > iii...
> -  *
> -  *   where 'p' represents an acquisition in process
> -  *   context, 'i' represents an acquisition in irq
> -  *   context.
> -  *
> -  * In this example, the ring buffer was overwritten by
> -  * acquisitions in irq context, that should be detected on
> -  * rollback or commit.
> -  */
> - unsigned int hist_id;
> -
> - /*
>* Seperate stack_trace data. This will be used at commit step.
>*/
>   struct stack_trace  trace;
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,9 +855,7 @@ struct task_struct {
>   unsigned int xhlock_idx;
>   /* For restoring at history boundaries */
>   unsigned int xhlock_idx_hist[XHLOCK_NR];
> - unsigned int hist_id;
> - /* For overwrite check at each context exit */
> - unsigned int hist_id_save[XHLOCK_NR];
> + unsigned int xhlock_idx_max;
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
>  {
>   struct task_struct *cur = current;
>  
> - if (cur->xhlocks) {
> + if (cur->xhlocks)
>   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> - cur->hist_id_save[c] = cur->hist_id;
> - }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
>   struct task_struct *cur = current;
> + unsigned int idx;
>  
> - if (cur->xhlocks) {
> - unsigned int idx = cur->xhlock_idx_hist[c];
> - struct hist_lock *h = (idx);
> -
> - cur->xhlock_idx = idx;
> -
> - /* Check if the ring was overwritten. */
> - if (h->hist_id != cur->hist_id_save[c])
> - invalidate_xhlock(h);
> - }
> + if (!cur->xhlocks)
> + return;
> +
> + idx = cur->xhlock_idx_hist[c];
> + cur->xhlock_idx = idx;
> +
> + /*
> +  * A bit of magic here.. this deals with rewinding the (cyclic) history
> +  * array further than its size. IOW. looses the complete history.
> +  *
> +  * We detect this by tracking the previous oldest entry we've (over)
> +  * written in @xhlock_idx_max, this means the next entry is the oldest
> +  * entry still in the buffer, ie. its tail.
> +  *
> +  * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
> +  * older than @xhlock_idx_max we know we've just wiped the entire
> +  * history.
> +  */
> + if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
> + return;
> +
> + /*
> +  * Now that we know the buffer is effectively empty, reset our state
> +  * such that it appears empty (without in fact clearing the entire
> +  * buffer).
> +  *
> +  * Pick @idx as the 'new' beginning, (re)set all save-points to not
> +  * rewind past it and reset the max. Then invalidate this idx such that
> +  * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
> +  * will return the _next_ entry, we'll not overwrite this invalid entry
> +  * until the entire buffer is full again.
> +  */
> + for (c = 0; c < XHLOCK_NR; c++)
> + cur->xhlock_idx_hist[c] = idx;
> + cur->xhlock_idx_max = idx;
> + invalidate_xhlock((idx));
> +}
> +
> +static inline unsigned int xhlock_idx_inc(void)
> +{
> + struct task_struct *cur = current;
> + unsigned int idx = ++cur->xhlock_idx;
> +
> + /*
> +  * As per the requirement in crossrelease_hist_end(), track the tail.
> +  */
> + if 

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Peter Zijlstra]

On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const 
> int line, const char *s)
>   */
>  void crossrelease_hist_start(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx_hist[c] = current->xhlock_idx;
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> + cur->hist_id_save[c] = cur->hist_id;
> + }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx = current->xhlock_idx_hist[c];
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + unsigned int idx = cur->xhlock_idx_hist[c];
> + struct hist_lock *h = (idx);
> +
> + cur->xhlock_idx = idx;
> +
> + /* Check if the ring was overwritten. */
> + if (h->hist_id != cur->hist_id_save[c])
> + invalidate_xhlock(h);
> + }
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
>   * Check if the xhlock is valid, which would be false if,
>   *
>   *1. Has not used after initializaion yet.
> + *2. Got invalidated.
>   *
>   * Remind hist_lock is implemented as a ring buffer.
>   */
> @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> + xhlock->hist_id = current->hist_id++;
>  
>   xhlock->trace.nr_entries = 0;
>   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;


Hehe, _another_ scheme...

Yes I think this works.. but I had just sort of understood the last one.

How about I do this on top? That I think is a combination of what I
proposed last and your single invalidate thing. Combined they solve the
problem with the least amount of extra storage (a single int).


---
Subject: lockdep: Simplify xhlock ring buffer invalidation
From: Peter Zijlstra 
Date: Wed Aug 9 15:31:27 CEST 2017


Signed-off-by: Peter Zijlstra (Intel) 
---
 include/linux/lockdep.h  |   20 ---
 include/linux/sched.h|4 --
 kernel/locking/lockdep.c |   82 ++-
 3 files changed, 54 insertions(+), 52 deletions(-)

--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,26 +284,6 @@ struct held_lock {
  */
 struct hist_lock {
/*
-* Id for each entry in the ring buffer. This is used to
-* decide whether the ring buffer was overwritten or not.
-*
-* For example,
-*
-*   |<--- hist_lock ring buffer size --->|
-*   pi
-* wrapped > iii...
-*
-*   where 'p' represents an acquisition in process
-*   context, 'i' represents an acquisition in irq
-*   context.
-*
-* In this example, the ring buffer was overwritten by
-* acquisitions in irq context, that should be detected on
-* rollback or commit.
-*/
-   unsigned int hist_id;
-
-   /*
 * Seperate stack_trace data. This will be used at commit step.
 */
struct stack_trace  trace;
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -855,9 +855,7 @@ struct task_struct {
unsigned int xhlock_idx;
/* For restoring at history boundaries */
unsigned int xhlock_idx_hist[XHLOCK_NR];
-   unsigned int hist_id;
-   /* For overwrite check at each context exit */
-   unsigned int hist_id_save[XHLOCK_NR];
+   unsigned int xhlock_idx_max;
 #endif
 
 #ifdef CONFIG_UBSAN
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
 {
struct task_struct *cur = current;
 
-   if (cur->xhlocks) {
+   if (cur->xhlocks)
cur->xhlock_idx_hist[c] = cur->xhlock_idx;
-   cur->hist_id_save[c] = cur->hist_id;
-   }
 }
 
 void crossrelease_hist_end(enum context_t c)
 {
struct task_struct *cur = current;
+   unsigned int idx;
 
-   if (cur->xhlocks) {
-   unsigned int idx = cur->xhlock_idx_hist[c];
-   struct hist_lock *h = (idx);
-
-   cur->xhlock_idx = idx;
-
-   /* Check if the ring was overwritten. */
-   if (h->hist_id != cur->hist_id_save[c])
-   invalidate_xhlock(h);
-   }
+   if (!cur->xhlocks)
+   return;
+
+   idx = cur->xhlock_idx_hist[c];
+   cur->xhlock_idx = idx;
+
+   /*
+* A bit of magic here.. this deals with rewinding the (cyclic) history
+   

Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Peter Zijlstra]

On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const 
> int line, const char *s)
>   */
>  void crossrelease_hist_start(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx_hist[c] = current->xhlock_idx;
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> + cur->hist_id_save[c] = cur->hist_id;
> + }
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
> - if (current->xhlocks)
> - current->xhlock_idx = current->xhlock_idx_hist[c];
> + struct task_struct *cur = current;
> +
> + if (cur->xhlocks) {
> + unsigned int idx = cur->xhlock_idx_hist[c];
> + struct hist_lock *h = (idx);
> +
> + cur->xhlock_idx = idx;
> +
> + /* Check if the ring was overwritten. */
> + if (h->hist_id != cur->hist_id_save[c])
> + invalidate_xhlock(h);
> + }
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
>   * Check if the xhlock is valid, which would be false if,
>   *
>   *1. Has not used after initializaion yet.
> + *2. Got invalidated.
>   *
>   * Remind hist_lock is implemented as a ring buffer.
>   */
> @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>   /* Initialize hist_lock's members */
>   xhlock->hlock = *hlock;
> + xhlock->hist_id = current->hist_id++;
>  
>   xhlock->trace.nr_entries = 0;
>   xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;


Hehe, _another_ scheme...

Yes I think this works.. but I had just sort of understood the last one.

How about I do this on top? That I think is a combination of what I
proposed last and your single invalidate thing. Combined they solve the
problem with the least amount of extra storage (a single int).


---
Subject: lockdep: Simplify xhlock ring buffer invalidation
From: Peter Zijlstra 
Date: Wed Aug 9 15:31:27 CEST 2017


Signed-off-by: Peter Zijlstra (Intel) 
---
 include/linux/lockdep.h  |   20 ---
 include/linux/sched.h|4 --
 kernel/locking/lockdep.c |   82 ++-
 3 files changed, 54 insertions(+), 52 deletions(-)

--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,26 +284,6 @@ struct held_lock {
  */
 struct hist_lock {
/*
-* Id for each entry in the ring buffer. This is used to
-* decide whether the ring buffer was overwritten or not.
-*
-* For example,
-*
-*   |<--- hist_lock ring buffer size --->|
-*   pi
-* wrapped > iii...
-*
-*   where 'p' represents an acquisition in process
-*   context, 'i' represents an acquisition in irq
-*   context.
-*
-* In this example, the ring buffer was overwritten by
-* acquisitions in irq context, that should be detected on
-* rollback or commit.
-*/
-   unsigned int hist_id;
-
-   /*
 * Seperate stack_trace data. This will be used at commit step.
 */
struct stack_trace  trace;
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -855,9 +855,7 @@ struct task_struct {
unsigned int xhlock_idx;
/* For restoring at history boundaries */
unsigned int xhlock_idx_hist[XHLOCK_NR];
-   unsigned int hist_id;
-   /* For overwrite check at each context exit */
-   unsigned int hist_id_save[XHLOCK_NR];
+   unsigned int xhlock_idx_max;
 #endif
 
 #ifdef CONFIG_UBSAN
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
 {
struct task_struct *cur = current;
 
-   if (cur->xhlocks) {
+   if (cur->xhlocks)
cur->xhlock_idx_hist[c] = cur->xhlock_idx;
-   cur->hist_id_save[c] = cur->hist_id;
-   }
 }
 
 void crossrelease_hist_end(enum context_t c)
 {
struct task_struct *cur = current;
+   unsigned int idx;
 
-   if (cur->xhlocks) {
-   unsigned int idx = cur->xhlock_idx_hist[c];
-   struct hist_lock *h = (idx);
-
-   cur->xhlock_idx = idx;
-
-   /* Check if the ring was overwritten. */
-   if (h->hist_id != cur->hist_id_save[c])
-   invalidate_xhlock(h);
-   }
+   if (!cur->xhlocks)
+   return;
+
+   idx = cur->xhlock_idx_hist[c];
+   cur->xhlock_idx = idx;
+
+   /*
+* A bit of magic here.. this deals with rewinding the (cyclic) history
+* array further than its size. IOW. looses 

[PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

The ring buffer can be overwritten by hardirq/softirq/work contexts.
That cases must be considered on rollback or commit. For example,

  |<-- hist_lock ring buffer size ->|
  iii
wrapped > iii

  where 'p' represents an acquisition in process context,
  'i' represents an acquisition in irq context.

On irq exit, crossrelease tries to rollback idx to original position,
but it should not because the entry already has been invalid by
overwriting 'i'. Avoid rollback or commit for entries overwritten.

Signed-off-by: Byungchul Park 
---
 include/linux/lockdep.h  | 20 +++
 include/linux/sched.h|  3 +++
 kernel/locking/lockdep.c | 52 +++-
 3 files changed, 70 insertions(+), 5 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 0c8a1b8..48c244c 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,6 +284,26 @@ struct held_lock {
  */
 struct hist_lock {
/*
+* Id for each entry in the ring buffer. This is used to
+* decide whether the ring buffer was overwritten or not.
+*
+* For example,
+*
+*   |<--- hist_lock ring buffer size --->|
+*   pi
+* wrapped > iii...
+*
+*   where 'p' represents an acquisition in process
+*   context, 'i' represents an acquisition in irq
+*   context.
+*
+* In this example, the ring buffer was overwritten by
+* acquisitions in irq context, that should be detected on
+* rollback or commit.
+*/
+   unsigned int hist_id;
+
+   /*
 * Seperate stack_trace data. This will be used at commit step.
 */
struct stack_trace  trace;
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5becef5..373466b 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -855,6 +855,9 @@ struct task_struct {
unsigned int xhlock_idx;
/* For restoring at history boundaries */
unsigned int xhlock_idx_hist[CONTEXT_NR];
+   unsigned int hist_id;
+   /* For overwrite check at each context exit */
+   unsigned int hist_id_save[CONTEXT_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index afd6e64..5168dac 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file, const int 
line, const char *s)
 static atomic_t cross_gen_id; /* Can be wrapped */
 
 /*
+ * Make an entry of the ring buffer invalid.
+ */
+static inline void invalidate_xhlock(struct hist_lock *xhlock)
+{
+   /*
+* Normally, xhlock->hlock.instance must be !NULL.
+*/
+   xhlock->hlock.instance = NULL;
+}
+
+/*
  * Lock history stacks; we have 3 nested lock history stacks:
  *
  *   Hard IRQ
@@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const int 
line, const char *s)
  */
 void crossrelease_hist_start(enum context_t c)
 {
-   if (current->xhlocks)
-   current->xhlock_idx_hist[c] = current->xhlock_idx;
+   struct task_struct *cur = current;
+
+   if (cur->xhlocks) {
+   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
+   cur->hist_id_save[c] = cur->hist_id;
+   }
 }
 
 void crossrelease_hist_end(enum context_t c)
 {
-   if (current->xhlocks)
-   current->xhlock_idx = current->xhlock_idx_hist[c];
+   struct task_struct *cur = current;
+
+   if (cur->xhlocks) {
+   unsigned int idx = cur->xhlock_idx_hist[c];
+   struct hist_lock *h = (idx);
+
+   cur->xhlock_idx = idx;
+
+   /* Check if the ring was overwritten. */
+   if (h->hist_id != cur->hist_id_save[c])
+   invalidate_xhlock(h);
+   }
 }
 
 static int cross_lock(struct lockdep_map *lock)
@@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
  * Check if the xhlock is valid, which would be false if,
  *
  *1. Has not used after initializaion yet.
+ *2. Got invalidated.
  *
  * Remind hist_lock is implemented as a ring buffer.
  */
@@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
 
/* Initialize hist_lock's members */
xhlock->hlock = *hlock;
+   xhlock->hist_id = current->hist_id++;
 
xhlock->trace.nr_entries = 0;
xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -4995,6 +5022,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct 
hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
unsigned int cur = 

[PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Byungchul Park]

The ring buffer can be overwritten by hardirq/softirq/work contexts.
That cases must be considered on rollback or commit. For example,

  |<-- hist_lock ring buffer size ->|
  iii
wrapped > iii

  where 'p' represents an acquisition in process context,
  'i' represents an acquisition in irq context.

On irq exit, crossrelease tries to rollback idx to original position,
but it should not because the entry already has been invalid by
overwriting 'i'. Avoid rollback or commit for entries overwritten.

Signed-off-by: Byungchul Park 
---
 include/linux/lockdep.h  | 20 +++
 include/linux/sched.h|  3 +++
 kernel/locking/lockdep.c | 52 +++-
 3 files changed, 70 insertions(+), 5 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 0c8a1b8..48c244c 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,6 +284,26 @@ struct held_lock {
  */
 struct hist_lock {
/*
+* Id for each entry in the ring buffer. This is used to
+* decide whether the ring buffer was overwritten or not.
+*
+* For example,
+*
+*   |<--- hist_lock ring buffer size --->|
+*   pi
+* wrapped > iii...
+*
+*   where 'p' represents an acquisition in process
+*   context, 'i' represents an acquisition in irq
+*   context.
+*
+* In this example, the ring buffer was overwritten by
+* acquisitions in irq context, that should be detected on
+* rollback or commit.
+*/
+   unsigned int hist_id;
+
+   /*
 * Seperate stack_trace data. This will be used at commit step.
 */
struct stack_trace  trace;
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5becef5..373466b 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -855,6 +855,9 @@ struct task_struct {
unsigned int xhlock_idx;
/* For restoring at history boundaries */
unsigned int xhlock_idx_hist[CONTEXT_NR];
+   unsigned int hist_id;
+   /* For overwrite check at each context exit */
+   unsigned int hist_id_save[CONTEXT_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index afd6e64..5168dac 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file, const int 
line, const char *s)
 static atomic_t cross_gen_id; /* Can be wrapped */
 
 /*
+ * Make an entry of the ring buffer invalid.
+ */
+static inline void invalidate_xhlock(struct hist_lock *xhlock)
+{
+   /*
+* Normally, xhlock->hlock.instance must be !NULL.
+*/
+   xhlock->hlock.instance = NULL;
+}
+
+/*
  * Lock history stacks; we have 3 nested lock history stacks:
  *
  *   Hard IRQ
@@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const int 
line, const char *s)
  */
 void crossrelease_hist_start(enum context_t c)
 {
-   if (current->xhlocks)
-   current->xhlock_idx_hist[c] = current->xhlock_idx;
+   struct task_struct *cur = current;
+
+   if (cur->xhlocks) {
+   cur->xhlock_idx_hist[c] = cur->xhlock_idx;
+   cur->hist_id_save[c] = cur->hist_id;
+   }
 }
 
 void crossrelease_hist_end(enum context_t c)
 {
-   if (current->xhlocks)
-   current->xhlock_idx = current->xhlock_idx_hist[c];
+   struct task_struct *cur = current;
+
+   if (cur->xhlocks) {
+   unsigned int idx = cur->xhlock_idx_hist[c];
+   struct hist_lock *h = (idx);
+
+   cur->xhlock_idx = idx;
+
+   /* Check if the ring was overwritten. */
+   if (h->hist_id != cur->hist_id_save[c])
+   invalidate_xhlock(h);
+   }
 }
 
 static int cross_lock(struct lockdep_map *lock)
@@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
  * Check if the xhlock is valid, which would be false if,
  *
  *1. Has not used after initializaion yet.
+ *2. Got invalidated.
  *
  * Remind hist_lock is implemented as a ring buffer.
  */
@@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
 
/* Initialize hist_lock's members */
xhlock->hlock = *hlock;
+   xhlock->hist_id = current->hist_id++;
 
xhlock->trace.nr_entries = 0;
xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -4995,6 +5022,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct 
hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
unsigned int cur = current->xhlock_idx;
+   unsigned