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