[PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Anton Vorontsov]

We'd like to use this function in the android low memory killer driver, so
let's export it.

Also, move next_tgid() to kernel/pid.c, so now it lives with the rest of
pid library functions and does not depend on procfs. Plus, we may now hide
find_ge_pid() from the global namespace.

While at it, also turn next_tgid()'s comments into kerneldoc format.

There should be no functional changes.

Signed-off-by: Anton Vorontsov <anton.vorontsov@linaro.org>
---
 fs/proc/base.c      |   43 -------------------------------------------
 include/linux/pid.h |    9 ++++++++-
 kernel/pid.c        |   41 ++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 48 insertions(+), 45 deletions(-)

diff --git a/fs/proc/base.c b/fs/proc/base.c
index 5485a53..84b8625 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -3324,49 +3324,6 @@ out:
 	return result;
 }
 
-/*
- * Find the first task with tgid >= tgid
- *
- */
-struct tgid_iter {
-	unsigned int tgid;
-	struct task_struct *task;
-};
-static struct tgid_iter next_tgid(struct pid_namespace *ns, struct tgid_iter iter)
-{
-	struct pid *pid;
-
-	if (iter.task)
-		put_task_struct(iter.task);
-	rcu_read_lock();
-retry:
-	iter.task = NULL;
-	pid = find_ge_pid(iter.tgid, ns);
-	if (pid) {
-		iter.tgid = pid_nr_ns(pid, ns);
-		iter.task = pid_task(pid, PIDTYPE_PID);
-		/* What we to know is if the pid we have find is the
-		 * pid of a thread_group_leader.  Testing for task
-		 * being a thread_group_leader is the obvious thing
-		 * todo but there is a window when it fails, due to
-		 * the pid transfer logic in de_thread.
-		 *
-		 * So we perform the straight forward test of seeing
-		 * if the pid we have found is the pid of a thread
-		 * group leader, and don't worry if the task we have
-		 * found doesn't happen to be a thread group leader.
-		 * As we don't care in the case of readdir.
-		 */
-		if (!iter.task || !has_group_leader_pid(iter.task)) {
-			iter.tgid += 1;
-			goto retry;
-		}
-		get_task_struct(iter.task);
-	}
-	rcu_read_unlock();
-	return iter;
-}
-
 #define TGID_OFFSET (FIRST_PROCESS_ENTRY + ARRAY_SIZE(proc_base_stuff))
 
 static int proc_pid_fill_cache(struct file *filp, void *dirent, filldir_t filldir,
diff --git a/include/linux/pid.h b/include/linux/pid.h
index b152d44..33e350b 100644
--- a/include/linux/pid.h
+++ b/include/linux/pid.h
@@ -116,7 +116,6 @@ extern struct pid *find_vpid(int nr);
  * Lookup a PID in the hash table, and return with it's count elevated.
  */
 extern struct pid *find_get_pid(int nr);
-extern struct pid *find_ge_pid(int nr, struct pid_namespace *);
 int next_pidmap(struct pid_namespace *pid_ns, unsigned int last);
 
 extern struct pid *alloc_pid(struct pid_namespace *ns);
@@ -199,4 +198,12 @@ pid_t pid_vnr(struct pid *pid);
 		} while_each_thread(tg___, task);			\
 		task = tg___;						\
 	} while_each_pid_task(pid, type, task)
+
+struct tgid_iter {
+	unsigned int tgid;
+	struct task_struct *task;
+};
+
+struct tgid_iter next_tgid(struct pid_namespace *ns, struct tgid_iter iter);
+
 #endif /* _LINUX_PID_H */
diff --git a/kernel/pid.c b/kernel/pid.c
index ce8e00d..34a52a6 100644
--- a/kernel/pid.c
+++ b/kernel/pid.c
@@ -522,7 +522,7 @@ EXPORT_SYMBOL_GPL(task_active_pid_ns);
  *
  * If there is a pid at nr this function is exactly the same as find_pid_ns.
  */
-struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
+static struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
 {
 	struct pid *pid;
 
@@ -536,6 +536,45 @@ struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
 	return pid;
 }
 
+/**
+ * next_tgid() - Find the first task with tgid >= tgid
+ * @ns: pointer to the pid namespace
+ * @iter: iterator
+ */
+struct tgid_iter next_tgid(struct pid_namespace *ns, struct tgid_iter iter)
+{
+	struct pid *pid;
+
+	if (iter.task)
+		put_task_struct(iter.task);
+	rcu_read_lock();
+retry:
+	iter.task = NULL;
+	pid = find_ge_pid(iter.tgid, ns);
+	if (pid) {
+		iter.tgid = pid_nr_ns(pid, ns);
+		iter.task = pid_task(pid, PIDTYPE_PID);
+		/* What we to know is if the pid we have find is the
+		 * pid of a thread_group_leader.  Testing for task
+		 * being a thread_group_leader is the obvious thing
+		 * todo but there is a window when it fails, due to
+		 * the pid transfer logic in de_thread.
+		 *
+		 * So we perform the straight forward test of seeing
+		 * if the pid we have found is the pid of a thread
+		 * group leader, and don't worry if the task we have
+		 * found doesn't happen to be a thread group leader.
+		 */
+		if (!iter.task || !has_group_leader_pid(iter.task)) {
+			iter.tgid += 1;
+			goto retry;
+		}
+		get_task_struct(iter.task);
+	}
+	rcu_read_unlock();
+	return iter;
+}
+
 /*
  * The pid hash table is scaled according to the amount of memory in the
  * machine.  From a minimum of 16 slots up to 4096 slots at one gigabyte or
-- 
1.7.7

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Greg KH]

On Mon, Jan 30, 2012 at 05:13:23AM +0400, Anton Vorontsov wrote:
> We'd like to use this function in the android low memory killer driver, so
> let's export it.

Why is it needed?

I _REALLY_ don't want to add any exports to any part of the kernel for
the android low memory stuff.  That is because it is not something that
should be touching anything else, especially as numerous people disagree
with what it does and how it does it.

Instead, you should be spending the time and effort to properly
implement this, as has been discussed numerous times, the last one a
mere few weeks ago when someone tried adding the nokia-specific low
memory killer/notifier code.

So no, sorry, I will not take these patches, unless you come up with
some very good justifications why.

greg k-h

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Eric W. Biederman]

Anton Vorontsov <anton.vorontsov@linaro.org> writes:

> We'd like to use this function in the android low memory killer driver, so
> let's export it.
>
> Also, move next_tgid() to kernel/pid.c, so now it lives with the rest of
> pid library functions and does not depend on procfs. Plus, we may now hide
> find_ge_pid() from the global namespace.
>
> While at it, also turn next_tgid()'s comments into kerneldoc format.
>
> There should be no functional changes.

Ouch no.

There is find_ge_pid that is general purpose, and there are a lot of
things with the task list.  But this iterator is specific to the
implementation of proc especially in how it grabs and drops locks.

Using this code outside of /proc will make /proc harder to maintain than
it already is.

Why in the world would you want to traverse processes by pids when
there are well defined iterators for looping over tasks already.

Eric

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Oleg Nesterov]

On 01/30, Anton Vorontsov wrote:
>
> We'd like to use this function in the android low memory killer driver, so
> let's export it.

I guess you mean 3/3.

If lowmem_shrink() can use next_tid() which is not really accurate,
then why tou can't simply change it to use rcu_read_lock ?

Oleg.

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Anton Vorontsov]

On Sun, Jan 29, 2012 at 06:22:42PM -0800, Greg KH wrote:
> On Mon, Jan 30, 2012 at 05:13:23AM +0400, Anton Vorontsov wrote:
> > We'd like to use this function in the android low memory killer driver, so
> > let's export it.
> 
> Why is it needed?
> 
> I _REALLY_ don't want to add any exports to any part of the kernel for
> the android low memory stuff.  That is because it is not something that
> should be touching anything else, especially as numerous people disagree
> with what it does and how it does it.
> 
> Instead, you should be spending the time and effort to properly
> implement this, as has been discussed numerous times, the last one a
> mere few weeks ago when someone tried adding the nokia-specific low
> memory killer/notifier code.

Yep, and I fully agree here. But doing it the right way (i.e. teaching
Android to use low memory notifiers) will take some time. And improving
current driver meanwhile is just my sub-task.

> So no, sorry, I will not take these patches, unless you come up with
> some very good justifications why.

Well, actually, this patches were born as a response to LMK review[1]
by KOSAKI Motohiro, he did not like the tasklist lock. Though, I agree
that it might be not a great idea to export API for the driver that
is about to superseded by a different approach (i.e. notifiers). :-)

Heh. But you never know where you'll end up before you actually
try to do something. I have tried to get rid of the tacklist lock,
and it appears that it causes more trouble. :-)

[1] http://lkml.org/lkml/2011/12/19/294

-- 
Anton Vorontsov
Email: cbouatmailru@gmail.com

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Anton Vorontsov]

On Sun, Jan 29, 2012 at 07:26:55PM -0800, Eric W. Biederman wrote:
> Anton Vorontsov <anton.vorontsov@linaro.org> writes:
> 
> > We'd like to use this function in the android low memory killer driver, so
> > let's export it.
> >
> > Also, move next_tgid() to kernel/pid.c, so now it lives with the rest of
> > pid library functions and does not depend on procfs. Plus, we may now hide
> > find_ge_pid() from the global namespace.
> >
> > While at it, also turn next_tgid()'s comments into kerneldoc format.
> >
> > There should be no functional changes.
> 
> Ouch no.
> 
> There is find_ge_pid that is general purpose, and there are a lot of
> things with the task list.  But this iterator is specific to the
> implementation of proc especially in how it grabs and drops locks.

Exactly, the way procfs grabs and drops locks is very attractive for
us to reuse in lowmemorykiller driver. :-) Proc is efficient in a
way that it does not need to hold the tacklist lock (otherwise, I guess,
it could be prone to attacks, e.g. by constantly readdiring /proc/ ?).

> Using this code outside of /proc will make /proc harder to maintain than
> it already is.
> 
> Why in the world would you want to traverse processes by pids when
> there are well defined iterators for looping over tasks already.

We just did not want to hold the global tasklist lock, if we could
avoid it. Low memory killer is a low priority stuff, and grabbing
tasklist lock seemed inefficient.

Thanks,

-- 
Anton Vorontsov
Email: cbouatmailru@gmail.com

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Anton Vorontsov]

On Mon, Jan 30, 2012 at 02:43:12PM +0100, Oleg Nesterov wrote:
> On 01/30, Anton Vorontsov wrote:
> >
> > We'd like to use this function in the android low memory killer driver, so
> > let's export it.
> 
> I guess you mean 3/3.
> 
> If lowmem_shrink() can use next_tid() which is not really accurate,
> then why tou can't simply change it to use rcu_read_lock ?

Yes, in LMK driver we don't need to be accurate. I probably could use
rcu_read_lock, but the plan was in not holding any global locks (in
this case the rcu) at all, instead I'd like to hold just a reference
of the task, which the driver is analyzing at this time. Once we decide
(to kill or not to kill the task), we either send a signal (and drop
the reference) or just drop the reference.

Thanks,

-- 
Anton Vorontsov
Email: cbouatmailru@gmail.com

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Eric W. Biederman]

Anton Vorontsov <anton.vorontsov@linaro.org> writes:

> On Mon, Jan 30, 2012 at 02:43:12PM +0100, Oleg Nesterov wrote:
>> On 01/30, Anton Vorontsov wrote:
>> >
>> > We'd like to use this function in the android low memory killer driver, so
>> > let's export it.
>> 
>> I guess you mean 3/3.
>> 
>> If lowmem_shrink() can use next_tid() which is not really accurate,
>> then why tou can't simply change it to use rcu_read_lock ?
>
> Yes, in LMK driver we don't need to be accurate. I probably could use
> rcu_read_lock, but the plan was in not holding any global locks (in
> this case the rcu) at all, instead I'd like to hold just a reference
> of the task, which the driver is analyzing at this time. Once we decide
> (to kill or not to kill the task), we either send a signal (and drop
> the reference) or just drop the reference.

rcu_read_lock unless it is implemented wrong is free from a lock
perspective.  rcu_read_lock only touches local state.

>From the look of your loop it already does a walk through the entire
process list so it looks to me like playing games with get_task_struct
and put_task_struct are going to be much more expensive.

proc grabs task references because we can't hold the rcu_read_lock
over a copy_to_user because that is a sleeping function.

You don't call anything that sleeps so rcu_read_lock should be
sufficient.

Eric

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Anton Vorontsov]

On Mon, Jan 30, 2012 at 05:51:20PM -0800, Eric W. Biederman wrote:
[...]
> > Yes, in LMK driver we don't need to be accurate. I probably could use
> > rcu_read_lock, but the plan was in not holding any global locks (in
> > this case the rcu) at all, instead I'd like to hold just a reference
> > of the task, which the driver is analyzing at this time. Once we decide
> > (to kill or not to kill the task), we either send a signal (and drop
> > the reference) or just drop the reference.
> 
> rcu_read_lock unless it is implemented wrong is free from a lock
> perspective.  rcu_read_lock only touches local state.
> 
> >From the look of your loop it already does a walk through the entire
> process list so it looks to me like playing games with get_task_struct
> and put_task_struct are going to be much more expensive.
> 
> proc grabs task references because we can't hold the rcu_read_lock
> over a copy_to_user because that is a sleeping function.
> 
> You don't call anything that sleeps so rcu_read_lock should be
> sufficient.

I'll just repeat what I told to Paul E. McKenney:

[...] the locking part wasn't my concern at all. As I said before,
LMK (low memory killer) itself is not important, and we don't care
about its overhead, unless it blocks another kernel activity --
which is my main concern.

So, reader part is not interesting in sense of overhead or
efficiency.

The interesting questions are:

1. Can the kernel create processes while LMK traverses the list?
2. Can the kernel free processes while LMK traverses the list?

Looking into kernel/fork.c:copy_process(), it does this:

- Takes a write lock on tasklist_lock;
- Uses list_add_tail_rcu() to add a task.

So, with current LMK driver (it grabs the tasklist_lock), it seems
that the kernel won't able to create processes while LMK traverse the
tasks.

Looking into kernel/exit.c:release_task(), it does this:

- Takes a write lock on tasklist_lock;
- Deletes the task from the list using list_del_rcu()
- Releases tasklist_lock;
- Issues call_rcu(&p->rcu, delayed_put_task_struct), which
  then actually completely frees the task;

So, with the current LMK driver, kernel won't able to release
processes while LMK traverse the processes, because LMK takes
the tasklist_lock.

By using rcu_read_lock() we would solve "1.", i.e. kernel will able
to create processes, but we still won't able to free processes (well,
for the most part we will, except that we'll only free memory after
LMK finishes its traverse).

(I still may be wrong in my findings, please correct me if so.)


Note the these aren't huge or catastrophic issues or something alike.
It is just that during LMK review people pointed out that grabbing
the tasklist lock for LMK is 'too much', and we'd better find a
better way.

rcu_read_lock() might be a good compromise.

Thanks,

-- 
Anton Vorontsov
Email: cbouatmailru@gmail.com

Re: [PATCH 1/3] procfs: Export next_tgid(), move it to kernel/pid.c

[Eric W. Biederman]

Anton Vorontsov <anton.vorontsov@linaro.org> writes:

> On Mon, Jan 30, 2012 at 05:51:20PM -0800, Eric W. Biederman wrote:
> [...]
>> > Yes, in LMK driver we don't need to be accurate. I probably could use
>> > rcu_read_lock, but the plan was in not holding any global locks (in
>> > this case the rcu) at all, instead I'd like to hold just a reference
>> > of the task, which the driver is analyzing at this time. Once we decide
>> > (to kill or not to kill the task), we either send a signal (and drop
>> > the reference) or just drop the reference.
>> 
>> rcu_read_lock unless it is implemented wrong is free from a lock
>> perspective.  rcu_read_lock only touches local state.
>> 
>> >From the look of your loop it already does a walk through the entire
>> process list so it looks to me like playing games with get_task_struct
>> and put_task_struct are going to be much more expensive.
>> 
>> proc grabs task references because we can't hold the rcu_read_lock
>> over a copy_to_user because that is a sleeping function.
>> 
>> You don't call anything that sleeps so rcu_read_lock should be
>> sufficient.
>
> I'll just repeat what I told to Paul E. McKenney:
>
> [...] the locking part wasn't my concern at all. As I said before,
> LMK (low memory killer) itself is not important, and we don't care
> about its overhead, unless it blocks another kernel activity --
> which is my main concern.
>
> So, reader part is not interesting in sense of overhead or
> efficiency.
>
> The interesting questions are:
>
> 1. Can the kernel create processes while LMK traverses the list?
> 2. Can the kernel free processes while LMK traverses the list?
>
> Looking into kernel/fork.c:copy_process(), it does this:
>
> - Takes a write lock on tasklist_lock;
> - Uses list_add_tail_rcu() to add a task.
>
> So, with current LMK driver (it grabs the tasklist_lock), it seems
> that the kernel won't able to create processes while LMK traverse the
> tasks.
>
> Looking into kernel/exit.c:release_task(), it does this:
>
> - Takes a write lock on tasklist_lock;
> - Deletes the task from the list using list_del_rcu()
> - Releases tasklist_lock;
> - Issues call_rcu(&p->rcu, delayed_put_task_struct), which
>   then actually completely frees the task;
>
> So, with the current LMK driver, kernel won't able to release
> processes while LMK traverse the processes, because LMK takes
> the tasklist_lock.
>
> By using rcu_read_lock() we would solve "1.", i.e. kernel will able
> to create processes, but we still won't able to free processes (well,
> for the most part we will, except that we'll only free memory after
> LMK finishes its traverse).


Correct. We will only free the task_struct after you release the
rcu_read_lock. Many of the other resources are freed before the
task_struct.  So most of the memory of a process should be freeable
even with the rcu_read_lock held.

Eric