lkml.org 
[lkml]   [2010]   [Jun]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: while_each_thread() under rcu_read_lock() is broken?
On Mon, Jun 21, 2010 at 07:09:19PM +0200, Oleg Nesterov wrote:
> On 06/18, Paul E. McKenney wrote:
> >
> > On Fri, Jun 18, 2010 at 09:34:03PM +0200, Oleg Nesterov wrote:
> > >
> > > #define XXX(t) ({
> > > struct task_struct *__prev = t;
> > > t = next_thread(t);
> > > t != g && t != __prev;
> > > })
> > >
> > > #define while_each_thread(g, t) \
> > > while (XXX(t))
> >
> > Isn't the above vulnerable to a pthread_create() immediately following
> > the offending exec()? Especially if the task doing the traversal is
> > preempted?
>
> Yes, thanks!
>
> > here are some techniques that might (or might not) help:
>
> To simplify, let's consider the concrete example,

Sounds very good!

> rcu_read_lock();
>
> g = t = returns_the_rcu_safe_task_struct_ptr();

This returns a pointer to the task struct of the current thread?
Or might this return a pointer some other thread's task struct?

> do {
> printk("%d\n", t->pid);
> } while_each_thread(g, t);
>
> rcu_read_unlock();
>
> Whatever we do, without tasklist/siglock this can obviously race
> with fork/exit/exec. It is OK to miss a thread, or print the pid
> of the already exited/released task.
>
> But it should not loop forever (the subject), and it should not
> print the same pid twice (ignoring pid reuse, of course).
>
> And, afaics, there are no problems with rcu magic per se, next_thread()
> always returns the task_struct we can safely dereference. The only
> problem is that while_each_thread() assumes that sooner or later
> next_thread() must reach the starting point, g.
>
> (zap_threads() is different, it must not miss a thread with ->mm
> we are going to dump, but it holds mmap_sem).

Indeed, the tough part is figuring out when you are done given that things
can come and go at will. Some additional tricks, in no particular order:

1. Always start at the group leader. Of course, the group leader
is probably permitted to leave any time it wants to, so this
is not sufficient in and of itself.

2. Maintain a separate task structure that flags the head of the
list. This separate structure is freed one RCU grace period
following the disappearance of the current group leader. This
should be quite robust, but "holy overhead, Batman!!!" (Apologies
for the American pop culture reference, but nothing else seemed
appropriate.)

3. Like #2, but reduce the storage overhead by using a structure
containing only the pointers and perhaps a few additional fields.
Set one of the bottom bits of one of the pointers to flag the fact
that this is a special structure, allowing the reader to take
note and do any additional checks required.

Of course, it is possible for a reader to be diverted onto a
new thread group, so it is then also possible that it needs
to return back to the previous thread group. The smaller structure
corresponding to the smaller structure might contain the
pointers required for it to make this transition.

Please note that a given thread group will have several of
these structures if several thread-group depart in quick
succession. The smaller structure would need to contain
enough information to allow the reader to thread back to
whatever group-leader task it started from. Which will likely
make managing the lifetimes of these smaller structures
"interesting"... Though this could be eased by maintaining
forward links as well as backwards links. Then when the
grace period expired, the corresponding backwards links could
be NULLed -- and a second grace period would likely be needed.

It is tempting to leave these special structs out of any
thread groups that have not yet had a leader depart, but this
is probably vulnerable to looping. (It might be possible to
avoid this, but additional checks are required.)

There are other approaches, but it is probably time for you to teach me
more about the requirements you face.

> > o Check ACCESS_ONCE(p->group_leader == g),
>
> but this assumeas that while_each_thread(g, t) always
> uses g == group_leader. zap_other_threads(), for example,
> starts with g == current and not necessarily the leader.
>
> > if false, restart
> > the traversal.
>
> I am not sure we should restart (don't pid the same pid twice),
> probably we should break the loop.
>
> So, I am thinking about the first attempt
>
> #define while_each_thread(g, t) \
> while ((t = next_thread(t)) != g && pid_alive(g))
>
> again. But this means while_each_thread() can miss more threads
> than it currently can under the same conditions. Correct, but
> not good.

OK, so we really want to complete the scan through the thread group, or
at least avoid introducing additional tendency to not complete the scan.
Good to know. ;-)

> And,
>
> > This of course might
> > require careful attention of the order of updates to ->group_leader
> > and the list pointers.
>
> Yes. At least the code above needs barriers, and I am not sure
> it can be really correct without more complications.

Agreed!

> > o Maintain an ->oldnext field that tracks the old pointer to
> > the next task for one RCU grace period after a de_thread()
> > operation. When the grace period expires (presumably via
> > call_rcu()), the ->oldnext field is set to NULL.
>
> Well, another field in task_struct...

Yeah, would be good to avoid this. Not sure it can be avoided, though.

> > o Do the de_thread() incrementally. So if the list is tasks A,
> > B, and C, in that order, and if we are de-thread()ing B,
> > then make A's pointer refer to C,
>
> This breaks while_each_thread() under tasklist/siglock. It must
> see all unhashed tasks.

Could de_thread() hold those locks in order to avoid that breakage?

> Oh. I'll try to think more, but I also hope someone else can suggest
> a simple solution.

;-)

> > > Please tell me I am wrong!
> >
> > It would take a braver man than me to say that Oleg Nesterov is wrong!
>
> Hmm. Given that you proved I was wrong in the first lines of your
> email, I do not know what to think ;)

Ah, but I didn't prove you wrong. Instead, I simply asked if you
were wrong. You supplied the proof. ;-)

Thanx, Paul


\
 
 \ /
  Last update: 2010-06-21 22:53    [W:0.387 / U:25.852 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site