Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1403161 > unrolled thread

Re: [PATCH 3/3] introduce task_rcu_dereference()

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 3/3] introduce task_rcu_dereference() Peter Zijlstra <peterz@infradead.org> - 2016-05-18 19:10 +0200
    Re: [PATCH 3/3] introduce task_rcu_dereference() Oleg Nesterov <oleg@redhat.com> - 2016-05-18 20:30 +0200
      Re: [PATCH 3/3] introduce task_rcu_dereference() Peter Zijlstra <peterz@infradead.org> - 2016-05-18 21:20 +0200
        Re: [PATCH 3/3] introduce task_rcu_dereference() Oleg Nesterov <oleg@redhat.com> - 2016-05-18 22:00 +0200
          Re: [PATCH 3/3] introduce task_rcu_dereference() Peter Zijlstra <peterz@infradead.org> - 2016-05-26 13:40 +0200

#1403161 — Re: [PATCH 3/3] introduce task_rcu_dereference()

So I keep coming back to this, and every time I look at it my brain
explodes.

On Mon, Oct 27, 2014 at 08:54:46PM +0100, Oleg Nesterov wrote:
> +struct task_struct *task_rcu_dereference(struct task_struct **ptask)
> +{
> +	struct task_struct *task;
> +	struct sighand_struct *sighand;

I think that needs: ' = NULL', because if

> +
> +	/*
> +	 * We need to verify that release_task() was not called and thus
> +	 * delayed_put_task_struct() can't run and drop the last reference
> +	 * before rcu_read_unlock(). We check task->sighand != NULL, but
> +	 * we can read the already freed and reused memory.
> +	 */
> + retry:
> +	task = rcu_dereference(*ptask);
> +	if (!task)
> +		return NULL;
> +
> +	probe_slab_address(&task->sighand, sighand);

this fails because of DEBUG_PAGE_ALLOC, we might not write to sighand at
all, and

> +	/*
> +	 * Pairs with atomic_dec_and_test(usage) in put_task_struct(task).
> +	 * If this task was already freed we can not miss the preceding
> +	 * update of this pointer.
> +	 */
> +	smp_rmb();
> +	if (unlikely(task != ACCESS_ONCE(*ptask)))
> +		goto retry;
> +
> +	/*
> +	 * Either this is the same task and we can trust sighand != NULL, or
> +	 * its memory was re-instantiated as another instance of task_struct.
> +	 * In the latter case the new task can not go away until another rcu
> +	 * gp pass, so the only problem is that sighand == NULL can be false
> +	 * positive but we can pretend we got this NULL before it was freed.
> +	 */
> +	if (sighand)

this will be inspecting random values on the stack.

> +		return task;
> +
> +	/*
> +	 * We could even eliminate the false positive mentioned above:
> +	 *
> +	 *	probe_slab_address(&task->sighand, sighand);
> +	 *	if (sighand)
> +	 *		goto retry;
> +	 *
> +	 * if sighand != NULL because we read the freed memory we should
> +	 * see the new pointer, otherwise we will likely return this task.
> +	 */
> +	return NULL;
> +}

This thing does more than rcu_dereference; because it also guarantees
that task->usage > 0 for the entire RCU section you do this under.
Because delayed_put_task_struct() will be delayed until at least the
matching rcu_read_unlock().


Should we instead create a primitive like try_get_task_struct() which
returns true if it got a reference? Because that is typically what
people end up doing..

A little like so?

---
 include/linux/sched.h |  2 ++
 kernel/exit.c         | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c   | 29 +++++++----------------------
 3 files changed, 55 insertions(+), 22 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 38526b67e787..b2baa4af04e1 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -2132,6 +2132,8 @@ static inline void put_task_struct(struct task_struct *t)
 		__put_task_struct(t);
 }
 
+struct task_struct *try_get_task_struct(struct task_struct **ptask);
+
 #ifdef CONFIG_VIRT_CPU_ACCOUNTING_GEN
 extern void task_cputime(struct task_struct *t,
 			 cputime_t *utime, cputime_t *stime);
diff --git a/kernel/exit.c b/kernel/exit.c
index fd90195667e1..a1670dfd587b 100644
--- a/kernel/exit.c
+++ b/kernel/exit.c
@@ -210,6 +210,52 @@ void release_task(struct task_struct *p)
 		goto repeat;
 }
 
+struct task_struct *try_get_task_struct(struct task_struct **ptask)
+{
+	struct sighand_struct *sighand = NULL;
+	struct task_struct *task = NULL;
+
+	rcu_read_lock();
+	/*
+	 * We need to verify that release_task() was not called and thus
+	 * delayed_put_task_struct() can't run and drop the last reference
+	 * before rcu_read_unlock(). We check task->sighand != NULL,
+	 * but we can read the already freed and reused memory.
+	 */
+retry:
+	task = rcu_dereference(*ptask);
+	if (!task)
+		goto unlock;
+
+	probe_kernel_address(&task->sighand, sighand);
+
+	/*
+	 * Pairs with atomic_dec_and_test() in put_task_struct(). If this task
+	 * was already freed we can not miss the preceding update of this
+	 * pointer.
+	 */
+	if (unlikely(task != READ_ONCE(*ptask)))
+		goto retry;
+
+	/*
+	 * Either this is the same task and we can trust sighand != NULL, or
+	 * its memory was re-instantiated as another instrance of task_struct.
+	 * In the latter case the new task can not go away until another RCU
+	 * GP pass, so the only problem is that sighand == NULL can be a false
+	 * positive, but we can pretend we got this NULL before it was freed.
+	 */
+	if (!sighand) {
+		task = NULL;
+		goto unlock;
+	}
+
+	get_task_struct(task);
+
+unlock:
+	rcu_read_unlock();
+	return task;
+}
+
 /*
  * Determine if a process group is "orphaned", according to the POSIX
  * definition in 2.2.2.52.  Orphaned process groups are not to be affected
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 218f8e83db73..1d3a410c481b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1374,30 +1374,15 @@ static void task_numa_compare(struct task_numa_env *env,
 	int dist = env->dist;
 	bool assigned = false;
 
-	rcu_read_lock();
-
-	raw_spin_lock_irq(&dst_rq->lock);
-	cur = dst_rq->curr;
-	/*
-	 * No need to move the exiting task or idle task.
-	 */
-	if ((cur->flags & PF_EXITING) || is_idle_task(cur))
-		cur = NULL;
-	else {
-		/*
-		 * The task_struct must be protected here to protect the
-		 * p->numa_faults access in the task_weight since the
-		 * numa_faults could already be freed in the following path:
-		 * finish_task_switch()
-		 *     --> put_task_struct()
-		 *         --> __put_task_struct()
-		 *             --> task_numa_free()
-		 */
-		get_task_struct(cur);
+	cur = try_get_task_struct(&dst_rq->curr);
+	if (cur) {
+		if ((cur->flags & PF_EXITING) || is_idle_task(cur)) {
+			put_task_struct(cur);
+			cur = NULL;
+		}
 	}
 
-	raw_spin_unlock_irq(&dst_rq->lock);
-
+	rcu_read_lock();
 	/*
 	 * Because we have preemption enabled we can get migrated around and
 	 * end try selecting ourselves (current == env->p) as a swap candidate.

[toc] | [next] | [standalone]

#1403211

On 05/18, Peter Zijlstra wrote:
>
> So I keep coming back to this, and every time I look at it my brain
> explodes.

Heh ;) I forgot about this completely.

> On Mon, Oct 27, 2014 at 08:54:46PM +0100, Oleg Nesterov wrote:
> > +struct task_struct *task_rcu_dereference(struct task_struct **ptask)
> > +{
> > +	struct task_struct *task;
> > +	struct sighand_struct *sighand;
>
> I think that needs: ' = NULL', because if
>
> > +
> > +	/*
> > +	 * We need to verify that release_task() was not called and thus
> > +	 * delayed_put_task_struct() can't run and drop the last reference
> > +	 * before rcu_read_unlock(). We check task->sighand != NULL, but
> > +	 * we can read the already freed and reused memory.
> > +	 */
> > + retry:
> > +	task = rcu_dereference(*ptask);
> > +	if (!task)
> > +		return NULL;
> > +
> > +	probe_slab_address(&task->sighand, sighand);
>
> this fails because of DEBUG_PAGE_ALLOC, we might not write to sighand at
> all, and
>
> > +	/*
> > +	 * Pairs with atomic_dec_and_test(usage) in put_task_struct(task).
> > +	 * If this task was already freed we can not miss the preceding
> > +	 * update of this pointer.
> > +	 */
> > +	smp_rmb();
> > +	if (unlikely(task != ACCESS_ONCE(*ptask)))
> > +		goto retry;
> > +
> > +	/*
> > +	 * Either this is the same task and we can trust sighand != NULL, or
> > +	 * its memory was re-instantiated as another instance of task_struct.
> > +	 * In the latter case the new task can not go away until another rcu
> > +	 * gp pass, so the only problem is that sighand == NULL can be false
> > +	 * positive but we can pretend we got this NULL before it was freed.
> > +	 */
> > +	if (sighand)
>
> this will be inspecting random values on the stack.

Yes, but thi_s doesn't differ from the case when we inspect the random value
if this task_struct was freed, then reallocated as another thing, then freed
and reallocated as task_struct again.

Please note the comment about the false positive above, and another one below:

> > +	 * We could even eliminate the false positive mentioned above:
> > +	 *
> > +	 *	probe_slab_address(&task->sighand, sighand);
> > +	 *	if (sighand)
> > +	 *		goto retry;

this one.

IOW. We can never know if we have a garbage in "sighand" or the real value,
this task_struct can be freed/reallocated when we do probe_slab_address().

And this is fine. We re-check that "task == *ptask" after that. Now we have
two different cases:

	1. This is actually the same task/task_struct. In this case
           sighand != NULL tells us it is still alive.

        2. This is another task which got the same memory for task_struct.
           We can't know this of course, and we can not trust sighand != NULL.

	   In this case we actually return a random value, but this is correct.

	   If we return NULL - we can pretend that we actually noticed that
	   *ptask was updated when the previous task has exited. Or pretend
	   that probe_slab_address(&sighand) reads NULL.

	   If we return the new task (because sighand is not NULL for any
	   reason) - this is fine too. This (new) task can't go away before
	   another gp pass.

	   And please note again the "We could even eliminate the false positive"
	   comment above (hmm, it should probably say false negative). We could
	   re-read task->sighand once again to avoid the falsely NULL.

	   But this case is very unlikely so I think we do not really care.

And perhaps this idea can find more users...

> This thing does more than rcu_dereference; because it also guarantees
> that task->usage > 0 for the entire RCU section you do this under.
> Because delayed_put_task_struct() will be delayed until at least the
> matching rcu_read_unlock().

Yes, yes, exactly.

> Should we instead create a primitive like try_get_task_struct() which
> returns true if it got a reference? Because that is typically what
> people end up doing..

Well, I won't really argue... but personally I'd prefer to leave it to
the caller. Note that task_rcu_dereference() doesn't even do rcu_read_lock().
It really acts as "rcu dereference".

I agree, try_get_task_struct(ptask) makes sense too, but it should be
implemented as a trivial wrapper on top of task_rcu_dereference().

Oleg.

[toc] | [prev] | [next] | [standalone]

#1403240

On Wed, May 18, 2016 at 08:23:18PM +0200, Oleg Nesterov wrote:
> IOW. We can never know if we have a garbage in "sighand" or the real value,
> this task_struct can be freed/reallocated when we do probe_slab_address().
> 
> And this is fine. We re-check that "task == *ptask" after that. Now we have
> two different cases:
> 
> 	1. This is actually the same task/task_struct. In this case
>            sighand != NULL tells us it is still alive.
> 
>         2. This is another task which got the same memory for task_struct.
>            We can't know this of course, and we can not trust sighand != NULL.
> 
> 	   In this case we actually return a random value, but this is correct.
> 
> 	   If we return NULL - we can pretend that we actually noticed that
> 	   *ptask was updated when the previous task has exited. Or pretend
> 	   that probe_slab_address(&sighand) reads NULL.
> 
> 	   If we return the new task (because sighand is not NULL for any
> 	   reason) - this is fine too. This (new) task can't go away before
> 	   another gp pass.
> 
> 	   And please note again the "We could even eliminate the false positive"
> 	   comment above (hmm, it should probably say false negative). We could
> 	   re-read task->sighand once again to avoid the falsely NULL.
> 
> 	   But this case is very unlikely so I think we do not really care.
> 

Ah right, lets stick that in.. :-)

OK, something like so then?

---
 include/linux/sched.h |  3 ++
 kernel/exit.c         | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/fair.c   | 29 +++++---------------
 3 files changed, 86 insertions(+), 22 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 1b43b45a22b9..7f90002e9344 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -2134,6 +2134,9 @@ static inline void put_task_struct(struct task_struct *t)
 		__put_task_struct(t);
 }
 
+struct task_struct *task_rcu_dereference(struct task_struct **ptask);
+struct task_struct *try_get_task_struct(struct task_struct **ptask);
+
 #ifdef CONFIG_VIRT_CPU_ACCOUNTING_GEN
 extern void task_cputime(struct task_struct *t,
 			 cputime_t *utime, cputime_t *stime);
diff --git a/kernel/exit.c b/kernel/exit.c
index fd90195667e1..58d7e05821ae 100644
--- a/kernel/exit.c
+++ b/kernel/exit.c
@@ -211,6 +211,82 @@ void release_task(struct task_struct *p)
 }
 
 /*
+ * Note that if this function returns a valid task_struct pointer (!NULL)
+ * task->usage must remain >0 for the duration of the RCU critical section.
+ */
+struct task_struct *task_rcu_dereference(struct task_struct **ptask)
+{
+	struct sighand_struct *sighand;
+	struct task_struct *task;
+
+	/*
+	 * We need to verify that release_task() was not called and thus
+	 * delayed_put_task_struct() can't run and drop the last reference
+	 * before rcu_read_unlock(). We check task->sighand != NULL,
+	 * but we can read the already freed and reused memory.
+	 */
+retry:
+	task = rcu_dereference(*ptask);
+	if (!task)
+		return NULL;
+
+	probe_kernel_address(&task->sighand, sighand);
+
+	/*
+	 * Pairs with atomic_dec_and_test() in put_task_struct(). If this task
+	 * was already freed we can not miss the preceding update of this
+	 * pointer.
+	 */
+	smp_rmb();
+	if (unlikely(task != READ_ONCE(*ptask)))
+		goto retry;
+
+	/*
+	 * We've re-checked that "task == *ptask", now we have two different
+	 * cases:
+	 *
+	 * 1. This is actually the same task/task_struct. In this case
+	 *    sighand != NULL tells us it is still alive.
+	 *
+	 * 2. This is another task which got the same memory for task_struct.
+	 *    We can't know this of course, and we can not trust
+	 *    sighand != NULL.
+	 *
+	 *    In this case we actually return a random value, but this is
+	 *    correct.
+	 *
+	 *    If we return NULL - we can pretend that we actually noticed that
+	 *    *ptask was updated when the previous task has exited. Or pretend
+	 *    that probe_slab_address(&sighand) reads NULL.
+	 *
+	 *    If we return the new task (because sighand is not NULL for any
+	 *    reason) - this is fine too. This (new) task can't go away before
+	 *    another gp pass.
+	 *
+	 *    And note: We could even eliminate the false positive if re-read
+	 *    task->sighand once again to avoid the falsely NULL. But this case
+	 *    is very unlikely so we don't care.
+	 */
+	if (!sighand)
+		return NULL;
+
+	return task;
+}
+
+struct task_struct *try_get_task_struct(struct task_struct **ptask)
+{
+	struct task_struct *task;
+
+	rcu_read_lock();
+	task = task_rcu_dereference(ptask);
+	if (task)
+		get_task_struct(task);
+	rcu_read_unlock();
+
+	return task;
+}
+
+/*
  * Determine if a process group is "orphaned", according to the POSIX
  * definition in 2.2.2.52.  Orphaned process groups are not to be affected
  * by terminal-generated stop signals.  Newly orphaned process groups are
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 218f8e83db73..1d3a410c481b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1374,30 +1374,15 @@ static void task_numa_compare(struct task_numa_env *env,
 	int dist = env->dist;
 	bool assigned = false;
 
-	rcu_read_lock();
-
-	raw_spin_lock_irq(&dst_rq->lock);
-	cur = dst_rq->curr;
-	/*
-	 * No need to move the exiting task or idle task.
-	 */
-	if ((cur->flags & PF_EXITING) || is_idle_task(cur))
-		cur = NULL;
-	else {
-		/*
-		 * The task_struct must be protected here to protect the
-		 * p->numa_faults access in the task_weight since the
-		 * numa_faults could already be freed in the following path:
-		 * finish_task_switch()
-		 *     --> put_task_struct()
-		 *         --> __put_task_struct()
-		 *             --> task_numa_free()
-		 */
-		get_task_struct(cur);
+	cur = try_get_task_struct(&dst_rq->curr);
+	if (cur) {
+		if ((cur->flags & PF_EXITING) || is_idle_task(cur)) {
+			put_task_struct(cur);
+			cur = NULL;
+		}
 	}
 
-	raw_spin_unlock_irq(&dst_rq->lock);
-
+	rcu_read_lock();
 	/*
 	 * Because we have preemption enabled we can get migrated around and
 	 * end try selecting ourselves (current == env->p) as a swap candidate.

[toc] | [prev] | [next] | [standalone]

#1403256

On 05/18, Peter Zijlstra wrote:
>
> OK, something like so then?

Yes thanks!

Just one note,

> +struct task_struct *task_rcu_dereference(struct task_struct **ptask)
> +{
> +	struct sighand_struct *sighand;
> +	struct task_struct *task;
> +
> +	/*
> +	 * We need to verify that release_task() was not called and thus
> +	 * delayed_put_task_struct() can't run and drop the last reference
> +	 * before rcu_read_unlock(). We check task->sighand != NULL,
> +	 * but we can read the already freed and reused memory.
> +	 */
> +retry:
> +	task = rcu_dereference(*ptask);
> +	if (!task)
> +		return NULL;
> +
> +	probe_kernel_address(&task->sighand, sighand);

OK. Then I'll re-send the patch which adds the probe_slab_address() helper
on top of this change. We do not want __probe_kernel_read() if
if CONFIG_DEBUG_PAGEALLOC=n.

> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1374,30 +1374,15 @@ static void task_numa_compare(struct task_numa_env *env,
>  	int dist = env->dist;
>  	bool assigned = false;
>  
> -	rcu_read_lock();
> -
> -	raw_spin_lock_irq(&dst_rq->lock);
> -	cur = dst_rq->curr;
> -	/*
> -	 * No need to move the exiting task or idle task.
> -	 */
> -	if ((cur->flags & PF_EXITING) || is_idle_task(cur))
> -		cur = NULL;
> -	else {
> -		/*
> -		 * The task_struct must be protected here to protect the
> -		 * p->numa_faults access in the task_weight since the
> -		 * numa_faults could already be freed in the following path:
> -		 * finish_task_switch()
> -		 *     --> put_task_struct()
> -		 *         --> __put_task_struct()
> -		 *             --> task_numa_free()
> -		 */
> -		get_task_struct(cur);
> +	cur = try_get_task_struct(&dst_rq->curr);

Do we really want try_get_task_struct() here? How about the change below?

To me it would be more clean to do get_task_struct() in task_numa_assign(),
it clearly pairs with put_task_struct(best_task) and task_numa_compare()
looks a bit simpler this way, no need to put_task_struct() if we nullify
cur.

What do you think? In any case I think the change in sched/fair.c should
probably come as a separate patch, but this is up to you.

Oleg.

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 40748dc..8e7083e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1254,6 +1254,8 @@ static void task_numa_assign(struct task_numa_env *env,
 {
 	if (env->best_task)
 		put_task_struct(env->best_task);
+	if (p)
+		get_task_struct(p);
 
 	env->best_task = p;
 	env->best_imp = imp;
@@ -1321,31 +1323,11 @@ static void task_numa_compare(struct task_numa_env *env,
 	long imp = env->p->numa_group ? groupimp : taskimp;
 	long moveimp = imp;
 	int dist = env->dist;
-	bool assigned = false;
 
 	rcu_read_lock();
-
-	raw_spin_lock_irq(&dst_rq->lock);
-	cur = dst_rq->curr;
-	/*
-	 * No need to move the exiting task or idle task.
-	 */
-	if ((cur->flags & PF_EXITING) || is_idle_task(cur))
+	cur = task_rcu_dereference(&dst_rq->curr);
+	if (cur && ((cur->flags & PF_EXITING) || is_idle_task(cur)))
 		cur = NULL;
-	else {
-		/*
-		 * The task_struct must be protected here to protect the
-		 * p->numa_faults access in the task_weight since the
-		 * numa_faults could already be freed in the following path:
-		 * finish_task_switch()
-		 *     --> put_task_struct()
-		 *         --> __put_task_struct()
-		 *             --> task_numa_free()
-		 */
-		get_task_struct(cur);
-	}
-
-	raw_spin_unlock_irq(&dst_rq->lock);
 
 	/*
 	 * Because we have preemption enabled we can get migrated around and
@@ -1428,7 +1410,6 @@ balance:
 		 */
 		if (!load_too_imbalanced(src_load, dst_load, env)) {
 			imp = moveimp - 1;
-			put_task_struct(cur);
 			cur = NULL;
 			goto assign;
 		}
@@ -1454,16 +1435,9 @@ balance:
 		env->dst_cpu = select_idle_sibling(env->p, env->dst_cpu);
 
 assign:
-	assigned = true;
 	task_numa_assign(env, cur, imp);
 unlock:
 	rcu_read_unlock();
-	/*
-	 * The dst_rq->curr isn't assigned. The protection for task_struct is
-	 * finished.
-	 */
-	if (cur && !assigned)
-		put_task_struct(cur);
 }
 
 static void task_numa_find_cpu(struct task_numa_env *env,

[toc] | [prev] | [next] | [standalone]

#1407528

On Wed, May 18, 2016 at 09:57:33PM +0200, Oleg Nesterov wrote:
> Do we really want try_get_task_struct() here? How about the change below?
> 
> To me it would be more clean to do get_task_struct() in task_numa_assign(),
> it clearly pairs with put_task_struct(best_task) and task_numa_compare()
> looks a bit simpler this way, no need to put_task_struct() if we nullify
> cur.
> 
> What do you think? In any case I think the change in sched/fair.c should
> probably come as a separate patch, but this is up to you.

You are quite right. I've added your SoB to this patch if you don't
mind -- and I've attributed the task_rcu_dereference() thing to you too,
as all I did was copy paste different bits of your emails together while
trying to get my head around it ;-)

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web