[PATCH] locking/lockdep: Use sched_clock() for random numbers.

[PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Sebastian Andrzej Siewior]

Since the rewrote of prandom_u32(), in the commit mentioned below, the
function uses sleeping locks which extracing random numbers and filling
the batch.
This breaks lockdep on PREEMPT_RT because lock_pin_lock() disables
interrupts while calling __lock_pin_lock(). This can't be moved earlier
because the main user of the function (rq_pin_lock()) invokes that
function after disabling interrupts in order to acquire the lock.

The cookie does not require random numbers as its goal is to provide a
random value in order to notice unexpected "unlock + lock" sites.

Use sched_clock() to provide random numbers.

Fixes: a0103f4d86f88 ("random32: use real rng for non-deterministic randomness")
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
---

So if the architecture does not provide sched_clock() and does not
enabled GENERIC_SCHED_CLOCK then we use jiffies here. Most of them do
one or the other except for alpha, csky, hexagon, ... but I don't worry
here since arm*, power*, x86* do provide it.

 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 81e87280513ea..f06b91ca6482d 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -5432,7 +5432,7 @@ static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
 			 * be guessable and still allows some pin nesting in
 			 * our u32 pin_count.
 			 */
-			cookie.val = 1 + (prandom_u32() >> 16);
+			cookie.val = 1 + (sched_clock() & 0xffff);
 			hlock->pin_count += cookie.val;
 			return cookie;
 		}
-- 
2.36.1

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Jason A. Donenfeld]

Hi Sebastian,

Interesting RT consideration. I hope there aren't too many of these
special cases that would necessitate a general mechanism. Fingers
crossed this is the only one.

On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
> -			cookie.val = 1 + (prandom_u32() >> 16);
> +			cookie.val = 1 + (sched_clock() & 0xffff);
>  			hlock->pin_count += cookie.val;
 
I have no idea what the requirements here are. What would happen if you
just did atomic_inc_return(&some_global) instead? That'd be faster
anyhow, and it's not like 16 bits gives you much variance anyway...

Jason

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Jason A. Donenfeld]

On Tue, May 17, 2022 at 11:53:43AM +0200, Jason A. Donenfeld wrote:
> Hi Sebastian,
> 
> Interesting RT consideration. I hope there aren't too many of these
> special cases that would necessitate a general mechanism. Fingers
> crossed this is the only one.
> 
> On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
> > -			cookie.val = 1 + (prandom_u32() >> 16);
> > +			cookie.val = 1 + (sched_clock() & 0xffff);
> >  			hlock->pin_count += cookie.val;
>  
> I have no idea what the requirements here are. What would happen if you
> just did atomic_inc_return(&some_global) instead? That'd be faster
> anyhow, and it's not like 16 bits gives you much variance anyway...

Also, what is that `1 +` doing there? If the intention is to make sure
this is non-zero, you might want the mask to be 0xfffe? Or you're
counting on the assigned type being a u32 so it all overflows into the
next zone the way you want it? Kinda weird.

Jason

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Sebastian Andrzej Siewior]

On 2022-05-17 11:59:19 [+0200], Jason A. Donenfeld wrote:
> On Tue, May 17, 2022 at 11:53:43AM +0200, Jason A. Donenfeld wrote:
> > Hi Sebastian,

Hi Jason,

> > Interesting RT consideration. I hope there aren't too many of these
> > special cases that would necessitate a general mechanism. Fingers
> > crossed this is the only one.

lockdep is special here. Haven't seen other explosions so far ;)

> > On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
> > > -			cookie.val = 1 + (prandom_u32() >> 16);
> > > +			cookie.val = 1 + (sched_clock() & 0xffff);
> > >  			hlock->pin_count += cookie.val;
> >  
> > I have no idea what the requirements here are. What would happen if you
> > just did atomic_inc_return(&some_global) instead? That'd be faster
> > anyhow, and it's not like 16 bits gives you much variance anyway...

it might work I guess. PeterZ? Would this_cpu_inc_return() work?

> Also, what is that `1 +` doing there? If the intention is to make sure
> this is non-zero, you might want the mask to be 0xfffe? Or you're
> counting on the assigned type being a u32 so it all overflows into the
> next zone the way you want it? Kinda weird.

hmm. It used to be 1 before prandom_u32() was introduced and the point
is probably to have a cookie != 0. val and pin_count are both unsigned
int/ 32bit so that overflow doesn't matter.

> Jason

Sebastian

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Sebastian Andrzej Siewior]

On 2022-05-17 11:16:14 [+0200], To linux-kernel@vger.kernel.org wrote:
> Since the rewrote of prandom_u32(), in the commit mentioned below, the
> function uses sleeping locks which extracing random numbers and filling
> the batch.
> This breaks lockdep on PREEMPT_RT because lock_pin_lock() disables
> interrupts while calling __lock_pin_lock(). This can't be moved earlier
> because the main user of the function (rq_pin_lock()) invokes that
> function after disabling interrupts in order to acquire the lock.
> 
> The cookie does not require random numbers as its goal is to provide a
> random value in order to notice unexpected "unlock + lock" sites.
> 
> Use sched_clock() to provide random numbers.
> 
> Fixes: a0103f4d86f88 ("random32: use real rng for non-deterministic randomness")
> Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
> ---
> 
> So if the architecture does not provide sched_clock() and does not
> enabled GENERIC_SCHED_CLOCK then we use jiffies here. Most of them do
> one or the other except for alpha, csky, hexagon, ... but I don't worry
> here since arm*, power*, x86* do provide it.

ping.

Jason suggested atomic_inc_return(&some_global).

>  kernel/locking/lockdep.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 81e87280513ea..f06b91ca6482d 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -5432,7 +5432,7 @@ static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
>  			 * be guessable and still allows some pin nesting in
>  			 * our u32 pin_count.
>  			 */
> -			cookie.val = 1 + (prandom_u32() >> 16);
> +			cookie.val = 1 + (sched_clock() & 0xffff);
>  			hlock->pin_count += cookie.val;
>  			return cookie;
>  		}

Sebastian

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Sasha Levin]

On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
>Since the rewrote of prandom_u32(), in the commit mentioned below, the
>function uses sleeping locks which extracing random numbers and filling
>the batch.
>This breaks lockdep on PREEMPT_RT because lock_pin_lock() disables
>interrupts while calling __lock_pin_lock(). This can't be moved earlier
>because the main user of the function (rq_pin_lock()) invokes that
>function after disabling interrupts in order to acquire the lock.
>
>The cookie does not require random numbers as its goal is to provide a
>random value in order to notice unexpected "unlock + lock" sites.
>
>Use sched_clock() to provide random numbers.
>
>Fixes: a0103f4d86f88 ("random32: use real rng for non-deterministic randomness")
>Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
>---
>
>So if the architecture does not provide sched_clock() and does not
>enabled GENERIC_SCHED_CLOCK then we use jiffies here. Most of them do
>one or the other except for alpha, csky, hexagon, ... but I don't worry
>here since arm*, power*, x86* do provide it.

I'm seeing hangs on AMD based machines with lockdep enabled, and
bisected the issue to a0103f4d86f88 ("random32: use real rng for
non-deterministic randomness").

No hangs on Intel/arm64, no hangs with lockdep disabled.

Spotted this patch on the list, and confirmed that it addresses the
issue I'm seeing.

-- 
Thanks,
Sasha

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Peter Zijlstra]

On Tue, May 17, 2022 at 11:53:43AM +0200, Jason A. Donenfeld wrote:
> Hi Sebastian,
> 
> Interesting RT consideration. I hope there aren't too many of these
> special cases that would necessitate a general mechanism. Fingers
> crossed this is the only one.
> 
> On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
> > -			cookie.val = 1 + (prandom_u32() >> 16);
> > +			cookie.val = 1 + (sched_clock() & 0xffff);
> >  			hlock->pin_count += cookie.val;
>  
> I have no idea what the requirements here are.

Mostly nothing. It's debug code, and if someone wants to circumvent they
can, but then their code is ugly and stands out like a sort thumb which
then serves its goal as it won't pass review etc..

> What would happen if you
> just did atomic_inc_return(&some_global) instead? That'd be faster
> anyhow, and it's not like 16 bits gives you much variance anyway...

That would in fact be slower, sched_clock() will, on any sane hardware,
be a rdtsc, mul and shr, which are all local.

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Peter Zijlstra]

On Tue, May 17, 2022 at 02:08:12PM +0200, Sebastian Andrzej Siewior wrote:
> On 2022-05-17 11:59:19 [+0200], Jason A. Donenfeld wrote:
> > On Tue, May 17, 2022 at 11:53:43AM +0200, Jason A. Donenfeld wrote:
> > > Hi Sebastian,
> 
> Hi Jason,
> 
> > > Interesting RT consideration. I hope there aren't too many of these
> > > special cases that would necessitate a general mechanism. Fingers
> > > crossed this is the only one.
> 
> lockdep is special here. Haven't seen other explosions so far ;)
> 
> > > On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
> > > > -			cookie.val = 1 + (prandom_u32() >> 16);
> > > > +			cookie.val = 1 + (sched_clock() & 0xffff);
> > > >  			hlock->pin_count += cookie.val;
> > >  
> > > I have no idea what the requirements here are. What would happen if you
> > > just did atomic_inc_return(&some_global) instead? That'd be faster
> > > anyhow, and it's not like 16 bits gives you much variance anyway...
> 
> it might work I guess. PeterZ? Would this_cpu_inc_return() work?

Probably. But sched_clock() is plenty fine enough. No need to waste
space on a variable.

> 
> > Also, what is that `1 +` doing there? If the intention is to make sure
> > this is non-zero, you might want the mask to be 0xfffe? Or you're
> > counting on the assigned type being a u32 so it all overflows into the
> > next zone the way you want it? Kinda weird.
> 
> hmm. It used to be 1 before prandom_u32() was introduced and the point
> is probably to have a cookie != 0. val and pin_count are both unsigned
> int/ 32bit so that overflow doesn't matter.

Right, must not be 0.

Re: [PATCH] locking/lockdep: Use sched_clock() for random numbers.

[Jason A. Donenfeld]

On Mon, Jun 13, 2022 at 10:05:43AM +0200, Peter Zijlstra wrote:
> On Tue, May 17, 2022 at 11:53:43AM +0200, Jason A. Donenfeld wrote:
> > Hi Sebastian,
> > 
> > Interesting RT consideration. I hope there aren't too many of these
> > special cases that would necessitate a general mechanism. Fingers
> > crossed this is the only one.
> > 
> > On Tue, May 17, 2022 at 11:16:14AM +0200, Sebastian Andrzej Siewior wrote:
> > > -			cookie.val = 1 + (prandom_u32() >> 16);
> > > +			cookie.val = 1 + (sched_clock() & 0xffff);
> > >  			hlock->pin_count += cookie.val;
> >  
> > I have no idea what the requirements here are.
> 
> Mostly nothing. It's debug code, and if someone wants to circumvent they
> can, but then their code is ugly and stands out like a sort thumb which
> then serves its goal as it won't pass review etc..
> 
> > What would happen if you
> > just did atomic_inc_return(&some_global) instead? That'd be faster
> > anyhow, and it's not like 16 bits gives you much variance anyway...
> 
> That would in fact be slower, sched_clock() will, on any sane hardware,
> be a rdtsc, mul and shr, which are all local.

Fine by me. Given Sasha's comment, we should probably get this queued up
in somebody's tree asap?

Jason

[tip: locking/urgent] locking/lockdep: Use sched_clock() for random numbers

[tip-bot2 for Sebastian Andrzej Siewior]

The following commit has been merged into the locking/urgent branch of tip:

Commit-ID:     4051a81774d6d8e28192742c26999d6f29bc0e68
Gitweb:        https://git.kernel.org/tip/4051a81774d6d8e28192742c26999d6f29bc0e68
Author:        Sebastian Andrzej Siewior <bigeasy@linutronix.de>
AuthorDate:    Tue, 17 May 2022 11:16:14 +02:00
Committer:     Peter Zijlstra <peterz@infradead.org>
CommitterDate: Mon, 13 Jun 2022 10:29:57 +02:00

locking/lockdep: Use sched_clock() for random numbers

Since the rewrote of prandom_u32(), in the commit mentioned below, the
function uses sleeping locks which extracing random numbers and filling
the batch.
This breaks lockdep on PREEMPT_RT because lock_pin_lock() disables
interrupts while calling __lock_pin_lock(). This can't be moved earlier
because the main user of the function (rq_pin_lock()) invokes that
function after disabling interrupts in order to acquire the lock.

The cookie does not require random numbers as its goal is to provide a
random value in order to notice unexpected "unlock + lock" sites.

Use sched_clock() to provide random numbers.

Fixes: a0103f4d86f88 ("random32: use real rng for non-deterministic randomness")
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://lkml.kernel.org/r/YoNn3pTkm5+QzE5k@linutronix.de
---
 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 81e8728..f06b91c 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -5432,7 +5432,7 @@ static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock)
 			 * be guessable and still allows some pin nesting in
 			 * our u32 pin_count.
 			 */
-			cookie.val = 1 + (prandom_u32() >> 16);
+			cookie.val = 1 + (sched_clock() & 0xffff);
 			hlock->pin_count += cookie.val;
 			return cookie;
 		}