kthread: Fix race condition between kthread_parkme() and kthread_unpark()

PATCH In review Junaid Shahid 4 participants 9 messages Apr 29, 2017 – Sep 29, 2017 1 message not in the archive

Share & tools

Junaid Shahid

author

2017-04-29 02:32 UTC #0 lore raw

PATCH 1/1 kthread: Fix race condition between kthread_parkme() and kthread_unpark()

In general, if kthread_unpark() and kthread_parkme() execute together, the kthread is supposed to be in an unparked state. This is because kthread_unpark() either wakes up the thread if it already got parked, or it cancels a prior kthread_park() call and hence renders the kthread_parkme() moot.

However, if kthread_unpark() happens to execute between the time that kthread_parkme() checks the KTHREAD_SHOULD_STOP flag and sets the KTHREAD_IS_PARKED flag, then kthread_unpark() will not wake up the thread and it will remain in a parked state.

This is fixed by making the checking of KTHREAD_SHOULD_STOP and the setting of KTHREAD_IS_PARKED atomic via a cmpxchg inside kthread_parkme.

Signed-off-by Junaid Shahid <[email protected]>

---
 kernel/kthread.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

kernel/kthread.c +12 -4

index 26db528c1d88..651f03baf62f 100644
@@ -169,12 +169,20 @@ void *kthread_probe_data(struct task_struct *task)
 
 static void __kthread_parkme(struct kthread *self)
 {
+	ulong flags;
+
 	__set_current_state(TASK_PARKED);
-	while (test_bit(KTHREAD_SHOULD_PARK, &self->flags)) {
-		if (!test_and_set_bit(KTHREAD_IS_PARKED, &self->flags))
-			complete(&self->parked);
-		schedule();
+	flags = self->flags;
+
+	while (test_bit(KTHREAD_SHOULD_PARK, &flags)) {
+		if (cmpxchg(&self->flags, flags,
+			    flags | (1 << KTHREAD_IS_PARKED)) == flags) {
+			if (!test_bit(KTHREAD_IS_PARKED, &flags))
+				complete(&self->parked);
+			schedule();
+		}
 		__set_current_state(TASK_PARKED);
+		flags = self->flags;
 	}
 	clear_bit(KTHREAD_IS_PARKED, &self->flags);
 	__set_current_state(TASK_RUNNING);

Signature · 1 line

2.13.0.rc0.306.g87b477812d-goog

Junaid Shahid

author

2017-05-30 22:37 UTC #1 lore raw

(Resending)

Quoted 49 lines · Junaid Shahid

In general, if kthread_unpark() and kthread_parkme() execute together, the kthread is supposed to be in an unparked state. This is because kthread_unpark() either wakes up the thread if it already got parked, or it cancels a prior kthread_park() call and hence renders the kthread_parkme() moot.
However, if kthread_unpark() happens to execute between the time that kthread_parkme() checks the KTHREAD_SHOULD_STOP flag and sets the KTHREAD_IS_PARKED flag, then kthread_unpark() will not wake up the thread and it will remain in a parked state.
This is fixed by making the checking of KTHREAD_SHOULD_STOP and the setting of KTHREAD_IS_PARKED atomic via a cmpxchg inside kthread_parkme.
Signed-off-by Junaid Shahid <[email protected]>
---
 kernel/kthread.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/kthread.c +12 -4
index 26db528c1d88..651f03baf62f 100644
@@ -169,12 +169,20 @@ void *kthread_probe_data(struct task_struct *task)
 
 static void __kthread_parkme(struct kthread *self)
 {
+	ulong flags;
+
 	__set_current_state(TASK_PARKED);
-	while (test_bit(KTHREAD_SHOULD_PARK, &self->flags)) {
-		if (!test_and_set_bit(KTHREAD_IS_PARKED, &self->flags))
-			complete(&self->parked);
-		schedule();
+	flags = self->flags;
+
+	while (test_bit(KTHREAD_SHOULD_PARK, &flags)) {
+		if (cmpxchg(&self->flags, flags,
+			    flags | (1 << KTHREAD_IS_PARKED)) == flags) {
+			if (!test_bit(KTHREAD_IS_PARKED, &flags))
+				complete(&self->parked);
+			schedule();
+		}
 		__set_current_state(TASK_PARKED);
+		flags = self->flags;
 	}
 	clear_bit(KTHREAD_IS_PARKED, &self->flags);
 	__set_current_state(TASK_RUNNING);

Andrew Morton

2017-05-30 22:40 UTC #2 lore raw

(cc tglx & tj)

Quoted 52 lines · On Tue, 30 May 2017 15:37:23 -0700 Junaid Shahid <[email protected]> wrote:

(Resending)
Quoted 49 lines · Junaid Shahid
In general, if kthread_unpark() and kthread_parkme() execute together, the kthread is supposed to be in an unparked state. This is because kthread_unpark() either wakes up the thread if it already got parked, or it cancels a prior kthread_park() call and hence renders the kthread_parkme() moot.
However, if kthread_unpark() happens to execute between the time that kthread_parkme() checks the KTHREAD_SHOULD_STOP flag and sets the KTHREAD_IS_PARKED flag, then kthread_unpark() will not wake up the thread and it will remain in a parked state.
This is fixed by making the checking of KTHREAD_SHOULD_STOP and the setting of KTHREAD_IS_PARKED atomic via a cmpxchg inside kthread_parkme.
Signed-off-by Junaid Shahid <[email protected]>
---
 kernel/kthread.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/kthread.c +12 -4
index 26db528c1d88..651f03baf62f 100644
@@ -169,12 +169,20 @@ void *kthread_probe_data(struct task_struct *task)
 
 static void __kthread_parkme(struct kthread *self)
 {
+	ulong flags;
+
 	__set_current_state(TASK_PARKED);
-	while (test_bit(KTHREAD_SHOULD_PARK, &self->flags)) {
-		if (!test_and_set_bit(KTHREAD_IS_PARKED, &self->flags))
-			complete(&self->parked);
-		schedule();
+	flags = self->flags;
+
+	while (test_bit(KTHREAD_SHOULD_PARK, &flags)) {
+		if (cmpxchg(&self->flags, flags,
+			    flags | (1 << KTHREAD_IS_PARKED)) == flags) {
+			if (!test_bit(KTHREAD_IS_PARKED, &flags))
+				complete(&self->parked);
+			schedule();
+		}
 		__set_current_state(TASK_PARKED);
+		flags = self->flags;
 	}
 	clear_bit(KTHREAD_IS_PARKED, &self->flags);
 	__set_current_state(TASK_RUNNING);

Junaid Shahid

author

2017-07-18 00:13 UTC #3 lore raw

Hi,

Has anyone been able to take a look at this?

Thanks,
Junaid

Quoted 56 lines · Andrew Morton

(cc tglx & tj)
Quoted 52 lines · On Tue, 30 May 2017 15:37:23 -0700 Junaid Shahid <[email protected]> wrote:
(Resending)
Quoted 49 lines · Junaid Shahid
In general, if kthread_unpark() and kthread_parkme() execute together, the kthread is supposed to be in an unparked state. This is because kthread_unpark() either wakes up the thread if it already got parked, or it cancels a prior kthread_park() call and hence renders the kthread_parkme() moot.
However, if kthread_unpark() happens to execute between the time that kthread_parkme() checks the KTHREAD_SHOULD_STOP flag and sets the KTHREAD_IS_PARKED flag, then kthread_unpark() will not wake up the thread and it will remain in a parked state.
This is fixed by making the checking of KTHREAD_SHOULD_STOP and the setting of KTHREAD_IS_PARKED atomic via a cmpxchg inside kthread_parkme.
Signed-off-by Junaid Shahid <[email protected]>
---
 kernel/kthread.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/kthread.c +12 -4
index 26db528c1d88..651f03baf62f 100644
@@ -169,12 +169,20 @@ void *kthread_probe_data(struct task_struct *task)
 
 static void __kthread_parkme(struct kthread *self)
 {
+	ulong flags;
+
 	__set_current_state(TASK_PARKED);
-	while (test_bit(KTHREAD_SHOULD_PARK, &self->flags)) {
-		if (!test_and_set_bit(KTHREAD_IS_PARKED, &self->flags))
-			complete(&self->parked);
-		schedule();
+	flags = self->flags;
+
+	while (test_bit(KTHREAD_SHOULD_PARK, &flags)) {
+		if (cmpxchg(&self->flags, flags,
+			    flags | (1 << KTHREAD_IS_PARKED)) == flags) {
+			if (!test_bit(KTHREAD_IS_PARKED, &flags))
+				complete(&self->parked);
+			schedule();
+		}
 		__set_current_state(TASK_PARKED);
+		flags = self->flags;
 	}
 	clear_bit(KTHREAD_IS_PARKED, &self->flags);
 	__set_current_state(TASK_RUNNING);

Thomas Gleixner

2017-07-18 06:35 UTC #4 lore raw

Quoted 3 lines · Junaid Shahid

Hi,
Has anyone been able to take a look at this?

Yes. It's in my pile of stuff to look at.

Peter Zijlstra

2017-09-27 12:17 UTC #5 lore raw

In reply to Junaid Shahid

Quoted 24 lines · Junaid Shahid

In general, if kthread_unpark() and kthread_parkme() execute together, the kthread is supposed to be in an unparked state. This is because kthread_unpark() either wakes up the thread if it already got parked, or it cancels a prior kthread_park() call and hence renders the kthread_parkme() moot.
However, if kthread_unpark() happens to execute between the time that kthread_parkme() checks the KTHREAD_SHOULD_STOP flag and sets the KTHREAD_IS_PARKED flag, then kthread_unpark() will not wake up the thread and it will remain in a parked state.
This is fixed by making the checking of KTHREAD_SHOULD_STOP and the setting of KTHREAD_IS_PARKED atomic via a cmpxchg inside kthread_parkme.
Signed-off-by Junaid Shahid <[email protected]>
---
 kernel/kthread.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/kthread.c +0 -0
index 26db528c1d88..651f03baf62f 100644

kernel/kthread.c void *kthread_probe_data(struct task_struct *task) · line 172

Quoted 4 lines

kernel/kthread.c +1 -0

@@ -169,12 +169,20 @@ void *kthread_probe_data(struct task_struct *task)
 
 static void __kthread_parkme(struct kthread *self)
 {
+	ulong flags;

That should be: "unsigned long".

kernel/kthread.c void *kthread_probe_data(struct task_struct *task) · line 175

Quoted 7 lines

kernel/kthread.c +2 -4

+
 	__set_current_state(TASK_PARKED);
-	while (test_bit(KTHREAD_SHOULD_PARK, &self->flags)) {
-		if (!test_and_set_bit(KTHREAD_IS_PARKED, &self->flags))
-			complete(&self->parked);
-		schedule();
+	flags = self->flags;

And at the very least, that should be:

	flags = READ_ONCE(self->flags);

kernel/kthread.c void *kthread_probe_data(struct task_struct *task) · line 177

Quoted 2 lines

kernel/kthread.c +2 -0

+
+	while (test_bit(KTHREAD_SHOULD_PARK, &flags)) {

Otherwise there's very little that stops the compiler from doing a reload here.

kernel/kthread.c void *kthread_probe_data(struct task_struct *task) · line 186

Quoted 9 lines

kernel/kthread.c +7 -0

+		if (cmpxchg(&self->flags, flags,
+			    flags | (1 << KTHREAD_IS_PARKED)) == flags) {
+			if (!test_bit(KTHREAD_IS_PARKED, &flags))
+				complete(&self->parked);
+			schedule();
+		}
 		__set_current_state(TASK_PARKED);
+		flags = self->flags;
 	}

That said, this is really quite horrible.

The alternative is of course changing kthread_unpark() to use a cmpxchg to clear SHOULD_PARK and then check IS_PARKED on its return value, but that's equally horrible.

How about something like the below? I still think its overly fragile, but barring more invasive changes the below more or less does as you suggest.

---

 kernel/kthread.c | 40 ++++++++++++++++++++++++++++++++++------
 1 file changed, 34 insertions(+), 6 deletions(-)

kernel/kthread.c +34 -6

index 1c19edf82427..f437f53f6fbc 100644
@@ -169,14 +169,38 @@ void *kthread_probe_data(struct task_struct *task)
 
 static void __kthread_parkme(struct kthread *self)
 {
-	__set_current_state(TASK_PARKED);
-	while (test_bit(KTHREAD_SHOULD_PARK, &self->flags)) {
-		if (!test_and_set_bit(KTHREAD_IS_PARKED, &self->flags))
-			complete(&self->parked);
-		schedule();
+	unsigned long flags;
+
+	for (;;) {
 		__set_current_state(TASK_PARKED);
+
+		/*
+		 * CPU0				CPU1
+		 *
+		 * [S] ->state = PARKED		[S]   ->flags &= ~SHOULD_PARK
+		 * [L] ->flags			[RmW] ->flags &= ~IS_PARKED
+		 * MB				MB
+		 * [RmW] ->flags |= IS_PARKED	wakeup()
+		 *
+		 * Thus, either CPU0 sets IS_PARKED and CPU1's wakeup must observe PARKED
+		 * or we observe !SHOULD_PARK and terminate.
+		 */
+
+		flags = READ_ONCE(self->flags);
+		if (!test_bit(KTHREAD_SHOULD_PARK, &flags))
+			break;
+
+		/*
+		 * Ensure SHOULD_PARK remains set while we set IS_PARKED.
+		 * Thereby we ensure kthread_unpark() cannot clear SHOULD_PARK
+		 * without us noticing.
+		 */
+
+		if (try_cmpxchg(&self->flags, &flags, flags | (1UL << KTHREAD_IS_PARKED))) {
+			complete(&self->parked);
+			schedule();
+		}
 	}
-	clear_bit(KTHREAD_IS_PARKED, &self->flags);
 	__set_current_state(TASK_RUNNING);
 }

@@ -454,6 +478,10 @@ void kthread_unpark(struct task_struct *k)
 		/*
 		 * Newly created kthread was parked when the CPU was offline.
 		 * The binding was lost and we need to set it again.
+		 *
+		 * Since we've observed IS_PARKED, the other thread will (have)
+		 * called schedule() and thus __kthread_bind()'s
+		 * wait_task_inactive() will succeed.
 		 */
 		if (test_bit(KTHREAD_IS_PER_CPU, &kthread->flags))
 			__kthread_bind(k, kthread->cpu, TASK_PARKED);

A message that is not in the archive (sent off-list or not yet received): CAL-GctE0BLVk=ps09dnir8pcpnfzg88jMK4CKkRVmY7-ho87nQ@mail.gmail.com

Thomas Gleixner

2017-09-29 08:00 UTC #7 lore raw

Quoted 10 lines · Junaid Shahid

Hi Peter,
It looks like try_cmpxchg is not available on non-x86 archs, but other than that the version that you proposed looks good.
One thing that I am a bit curious about is that the original code, before either patch, had a test_and_set_bit for KTHREAD_IS_PARKED rather than just a set_bit. I can't think of any reason why that was needed, since it doesn't look like TASK_PARKED tasks are susceptible to spurious wakeups. Do you by any chance happen to know if there was any specific reason for it?

Everything is susceptible to spurious wakeups and has to deal with it.

Thanks,

tglx

Peter Zijlstra

2017-09-29 08:28 UTC #8 lore raw

Quoted 7 lines · Thomas Gleixner

Quoted 5 lines · Junaid Shahid
Hi Peter,
It looks like try_cmpxchg is not available on non-x86 archs, but other than that the version that you proposed looks good.

Quoted 7 lines

Quoted 5 lines
One thing that I am a bit curious about is that the original code, before either patch, had a test_and_set_bit for KTHREAD_IS_PARKED rather than just a set_bit. I can't think of any reason why that was needed, since it doesn't look like TASK_PARKED tasks are susceptible to spurious wakeups. Do you by any chance happen to know if there was any specific reason for it?
Everything is susceptible to spurious wakeups and has to deal with it.

Right, we should code as if they are at all times possible. Currently, for TASK_PARKED, I don't think they can happen, but I've had patches that introduce them on purpose (regardless the state) just to stress the code.

IIRC only TASK_STOPPED and/or TASK_TRACED hard rely on not getting any.

Junaid Shahid

author

2017-09-29 20:58 UTC #9 lore raw

Thanks for the clarification. But in that case, shouldn’t the patch check whether IS_PARKED was already set before calling complete(&self->parked)? Otherwise, the completion count for self->parked could be more than 1 as a result of spurious wakeups, which could make a future call to kthread_park complete prematurely.

Thanks,
Junaid

Quoted 22 lines · Peter Zijlstra

Quoted 7 lines · Thomas Gleixner
Quoted 5 lines · Junaid Shahid
Hi Peter,
It looks like try_cmpxchg is not available on non-x86 archs, but other than that the version that you proposed looks good.
Quoted 7 lines
Quoted 5 lines
One thing that I am a bit curious about is that the original code, before either patch, had a test_and_set_bit for KTHREAD_IS_PARKED rather than just a set_bit. I can't think of any reason why that was needed, since it doesn't look like TASK_PARKED tasks are susceptible to spurious wakeups. Do you by any chance happen to know if there was any specific reason for it?
Everything is susceptible to spurious wakeups and has to deal with it.
Right, we should code as if they are at all times possible. Currently, for TASK_PARKED, I don't think they can happen, but I've had patches that introduce them on purpose (regardless the state) just to stress the code.
IIRC only TASK_STOPPED and/or TASK_TRACED hard rely on not getting any.