Skip to contentSkip to conversation

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

PATCH Applied Sebastian Andrzej Siewior 5 participants 10 messages May 17, 2022 – Jun 13, 2022 Locking primitives

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 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")

---

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(-)
kernel/locking/lockdep.c +1 -1
index 81e87280513ea..f06b91ca6482d 100644
@@ -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;
 		}
Signature · 1 line
2.36.1
#1 lore raw

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.

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5436

Quoted 3 lines · Sebastian Andrzej Siewior
kernel/locking/lockdep.c +1 -1
-			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

#2 lore raw
Quoted 6 lines · 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.

Quoted 8 lines

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5436

Quoted 3 lines · Sebastian Andrzej Siewior
kernel/locking/lockdep.c +1 -1
-			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

#3 lore raw
Quoted 2 lines · Jason A. Donenfeld
Quoted 1 line · Jason A. Donenfeld

Hi Sebastian,

Hi Jason,

Quoted 3 lines
Quoted 3 lines

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 ;)

Quoted 8 lines
Quoted 8 lines · Sebastian Andrzej Siewior

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5436

Quoted 3 lines
kernel/locking/lockdep.c +1 -1
-			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?

Quoted 4 lines

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.

Quoted 1 line

Jason

Sebastian

maintainer
#4 lore raw
Quoted 21 lines · Sebastian Andrzej Siewior
Quoted 2 lines · Jason A. Donenfeld
Quoted 1 line · Jason A. Donenfeld

Hi Sebastian,

Hi Jason,

Quoted 3 lines
Quoted 3 lines

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 ;)

Quoted 8 lines
Quoted 8 lines · Sebastian Andrzej Siewior

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5436

Quoted 3 lines
kernel/locking/lockdep.c +1 -1
-			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...

Quoted 1 line

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.

Quoted 9 lines
Quoted 5 lines

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.

maintainer
#5 lore raw
In reply to Jason A. Donenfeld
Quoted 6 lines · 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.

Quoted 6 lines

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5436

Quoted 3 lines · Sebastian Andrzej Siewior
kernel/locking/lockdep.c +1 -1
-			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..

Quoted 3 lines

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.

#6 lore raw
Quoted 18 lines · Peter Zijlstra
Quoted 6 lines · 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.

Quoted 6 lines

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5436

Quoted 3 lines · Sebastian Andrzej Siewior
kernel/locking/lockdep.c +1 -1
-			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..

Quoted 6 lines
Quoted 3 lines

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

#7 lore raw
In reply to Sebastian Andrzej Siewior
Quoted 13 lines · On 2022-05-17 11:16:14 [+0200], To [email protected] 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.

Quoted 8 lines
Fixes a0103f4d86f88 ("random32: use real rng for non-deterministic randomness")

---

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

Quoted 8 lines
 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/locking/lockdep.c +0 -0
index 81e87280513ea..f06b91ca6482d 100644

kernel/locking/lockdep.c static struct pin_cookie __lock_pin_lock(struct lockdep_map *lock) · line 5438

Quoted 8 lines
kernel/locking/lockdep.c +1 -1
@@ -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

#8 lore raw
In reply to Sebastian Andrzej Siewior
Quoted 13 lines · 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.

Quoted 8 lines
Fixes a0103f4d86f88 ("random32: use real rng for non-deterministic randomness")

---

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.

Signature · 2 lines
Thanks,
Sasha
#9 lore raw

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

In reply to Sebastian Andrzej Siewior
The following commit has been merged into the locking/urgent branch of tip:

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 <[email protected]>
AuthorDate:    Tue, 17 May 2022 11:16:14 +02:00
Committer:     Peter Zijlstra <[email protected]>
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")
---
 kernel/locking/lockdep.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/locking/lockdep.c +1 -1
index 81e8728..f06b91c 100644
@@ -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;
 		}