[PATCH] oom_reaper: switch to struct list_head for reap queue

[PATCH] oom_reaper: switch to struct list_head for reap queue

[Aleksa Sarai]

Rather than implementing an open addressing linked list structure
ourselves, use the standard list_head structure to improve consistency
with the rest of the kernel and reduce confusion.

Cc: Michal Hocko <mhocko@suse.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Signed-off-by: Aleksa Sarai <asarai@suse.de>
---
 include/linux/sched.h |  6 +++++-
 kernel/fork.c         |  4 ++++
 mm/oom_kill.c         | 24 +++++++++++++-----------
 3 files changed, 22 insertions(+), 12 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index e93594b88130..d8bcd0f8c5fe 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1960,7 +1960,11 @@ struct task_struct {
 #endif
 	int pagefault_disabled;
 #ifdef CONFIG_MMU
-	struct task_struct *oom_reaper_list;
+	/*
+	 * List of threads that have to be reaped by OOM (rooted at
+	 * &oom_reaper_list in mm/oom_kill.c).
+	 */
+	struct list_head oom_reaper_list;
 #endif
 #ifdef CONFIG_VMAP_STACK
 	struct vm_struct *stack_vm_area;
diff --git a/kernel/fork.c b/kernel/fork.c
index 5908f9fba21b..faca59865b1d 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1165,6 +1165,10 @@ static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
 	tsk->last_switch_count = tsk->nvcsw + tsk->nivcsw;
 #endif
 
+#ifdef CONFIG_MMU
+	INIT_LIST_HEAD(&tsk->oom_reaper_list);
+#endif
+
 	tsk->mm = NULL;
 	tsk->active_mm = NULL;
 
diff --git a/mm/oom_kill.c b/mm/oom_kill.c
index 51c091849dcb..d6b63ef52b88 100644
--- a/mm/oom_kill.c
+++ b/mm/oom_kill.c
@@ -1,6 +1,6 @@
 /*
  *  linux/mm/oom_kill.c
- * 
+ *
  *  Copyright (C)  1998,2000  Rik van Riel
  *	Thanks go out to Claus Fischer for some serious inspiration and
  *	for goading me into coding this file...
@@ -460,7 +460,7 @@ bool process_shares_mm(struct task_struct *p, struct mm_struct *mm)
  */
 static struct task_struct *oom_reaper_th;
 static DECLARE_WAIT_QUEUE_HEAD(oom_reaper_wait);
-static struct task_struct *oom_reaper_list;
+static LIST_HEAD(oom_reaper_list);
 static DEFINE_SPINLOCK(oom_reaper_lock);
 
 static bool __oom_reap_task_mm(struct task_struct *tsk, struct mm_struct *mm)
@@ -565,7 +565,7 @@ static void oom_reap_task(struct task_struct *tsk)
 	debug_show_all_locks();
 
 done:
-	tsk->oom_reaper_list = NULL;
+	list_del_init(&tsk->oom_reaper_list);
 
 	/*
 	 * Hide this mm from OOM killer because it has been either reaped or
@@ -582,12 +582,15 @@ static int oom_reaper(void *unused)
 	while (true) {
 		struct task_struct *tsk = NULL;
 
-		wait_event_freezable(oom_reaper_wait, oom_reaper_list != NULL);
+		wait_event_freezable(oom_reaper_wait,
+				     !list_empty(&oom_reaper_list));
+
 		spin_lock(&oom_reaper_lock);
-		if (oom_reaper_list != NULL) {
-			tsk = oom_reaper_list;
-			oom_reaper_list = tsk->oom_reaper_list;
-		}
+		tsk = list_first_entry_or_null(&oom_reaper_list,
+					       struct task_struct,
+					       oom_reaper_list);
+		if (tsk)
+			list_del_init(&tsk->oom_reaper_list);
 		spin_unlock(&oom_reaper_lock);
 
 		if (tsk)
@@ -603,14 +606,13 @@ static void wake_oom_reaper(struct task_struct *tsk)
 		return;
 
 	/* tsk is already queued? */
-	if (tsk == oom_reaper_list || tsk->oom_reaper_list)
+	if (!list_empty(&tsk->oom_reaper_list))
 		return;
 
 	get_task_struct(tsk);
 
 	spin_lock(&oom_reaper_lock);
-	tsk->oom_reaper_list = oom_reaper_list;
-	oom_reaper_list = tsk;
+	list_add_tail(&tsk->oom_reaper_list, &oom_reaper_list);
 	spin_unlock(&oom_reaper_lock);
 	wake_up(&oom_reaper_wait);
 }
-- 
2.11.0

Re: [PATCH] oom_reaper: switch to struct list_head for reap queue

[Johannes Weiner]

On Wed, Feb 15, 2017 at 02:07:14AM +1100, Aleksa Sarai wrote:
> Rather than implementing an open addressing linked list structure
> ourselves, use the standard list_head structure to improve consistency
> with the rest of the kernel and reduce confusion.
> 
> Cc: Michal Hocko <mhocko@suse.com>
> Cc: Oleg Nesterov <oleg@redhat.com>
> Signed-off-by: Aleksa Sarai <asarai@suse.de>
> ---
>  include/linux/sched.h |  6 +++++-
>  kernel/fork.c         |  4 ++++
>  mm/oom_kill.c         | 24 +++++++++++++-----------
>  3 files changed, 22 insertions(+), 12 deletions(-)
> 
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index e93594b88130..d8bcd0f8c5fe 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -1960,7 +1960,11 @@ struct task_struct {
>  #endif
>  	int pagefault_disabled;
>  #ifdef CONFIG_MMU
> -	struct task_struct *oom_reaper_list;
> +	/*
> +	 * List of threads that have to be reaped by OOM (rooted at
> +	 * &oom_reaper_list in mm/oom_kill.c).
> +	 */
> +	struct list_head oom_reaper_list;

This is an extra pointer to task_struct and more lines of code to
accomplish the same thing. Why would we want to do that?

Re: [PATCH] oom_reaper: switch to struct list_head for reap queue

[Aleksa Sarai]

>> Rather than implementing an open addressing linked list structure
>> ourselves, use the standard list_head structure to improve consistency
>> with the rest of the kernel and reduce confusion.
>>
>> Cc: Michal Hocko <mhocko@suse.com>
>> Cc: Oleg Nesterov <oleg@redhat.com>
>> Signed-off-by: Aleksa Sarai <asarai@suse.de>
>> ---
>>  include/linux/sched.h |  6 +++++-
>>  kernel/fork.c         |  4 ++++
>>  mm/oom_kill.c         | 24 +++++++++++++-----------
>>  3 files changed, 22 insertions(+), 12 deletions(-)
>>
>> diff --git a/include/linux/sched.h b/include/linux/sched.h
>> index e93594b88130..d8bcd0f8c5fe 100644
>> --- a/include/linux/sched.h
>> +++ b/include/linux/sched.h
>> @@ -1960,7 +1960,11 @@ struct task_struct {
>>  #endif
>>  	int pagefault_disabled;
>>  #ifdef CONFIG_MMU
>> -	struct task_struct *oom_reaper_list;
>> +	/*
>> +	 * List of threads that have to be reaped by OOM (rooted at
>> +	 * &oom_reaper_list in mm/oom_kill.c).
>> +	 */
>> +	struct list_head oom_reaper_list;
>
> This is an extra pointer to task_struct and more lines of code to
> accomplish the same thing. Why would we want to do that?

I don't think it's more "actual" lines of code (I think the wrapping is 
inflating the line number count), but switching it means that it's more 
in line with other queues in the kernel (it took me a bit to figure out 
what was going on with oom_reaper_list beforehand).

-- 
Aleksa Sarai
Software Engineer (Containers)
SUSE Linux GmbH
https://www.cyphar.com/

Re: [PATCH] oom_reaper: switch to struct list_head for reap queue

[Oleg Nesterov]

On 02/15, Aleksa Sarai wrote:
>
> >This is an extra pointer to task_struct and more lines of code to
> >accomplish the same thing. Why would we want to do that?
>
> I don't think it's more "actual" lines of code (I think the wrapping is
> inflating the line number count),

I too think it doesn't make sense to blow task_struct and the generated code.
And to me this patch doesn't make the source code more clean.

> but switching it means that it's more in
> line with other queues in the kernel (it took me a bit to figure out what
> was going on with oom_reaper_list beforehand).

perhaps you can turn oom_reaper_list into llist_head then. This will also
allow to remove oom_reaper_lock. Not sure this makes sense too.

Oleg.

Re: [PATCH] oom_reaper: switch to struct list_head for reap queue

[Ingo Molnar]

* Aleksa Sarai <asarai@suse.de> wrote:

> >>Rather than implementing an open addressing linked list structure
> >>ourselves, use the standard list_head structure to improve consistency
> >>with the rest of the kernel and reduce confusion.
> >>
> >>Cc: Michal Hocko <mhocko@suse.com>
> >>Cc: Oleg Nesterov <oleg@redhat.com>
> >>Signed-off-by: Aleksa Sarai <asarai@suse.de>
> >>---
> >> include/linux/sched.h |  6 +++++-
> >> kernel/fork.c         |  4 ++++
> >> mm/oom_kill.c         | 24 +++++++++++++-----------
> >> 3 files changed, 22 insertions(+), 12 deletions(-)
> >>
> >>diff --git a/include/linux/sched.h b/include/linux/sched.h
> >>index e93594b88130..d8bcd0f8c5fe 100644
> >>--- a/include/linux/sched.h
> >>+++ b/include/linux/sched.h
> >>@@ -1960,7 +1960,11 @@ struct task_struct {
> >> #endif
> >> 	int pagefault_disabled;
> >> #ifdef CONFIG_MMU
> >>-	struct task_struct *oom_reaper_list;
> >>+	/*
> >>+	 * List of threads that have to be reaped by OOM (rooted at
> >>+	 * &oom_reaper_list in mm/oom_kill.c).
> >>+	 */
> >>+	struct list_head oom_reaper_list;
> >
> >This is an extra pointer to task_struct and more lines of code to
> >accomplish the same thing. Why would we want to do that?
> 
> I don't think it's more "actual" lines of code (I think the wrapping is
> inflating the line number count), but switching it means that it's more in
> line with other queues in the kernel (it took me a bit to figure out what
> was going on with oom_reaper_list beforehand).

It's still an extra pointer and extra generated code to do the same thing - a clear step backwards.

Thanks,

	Ingo

Re: [PATCH] oom_reaper: switch to struct list_head for reap queue

[Aleksa Sarai]

>>> This is an extra pointer to task_struct and more lines of code to
>>> accomplish the same thing. Why would we want to do that?
>>
>> I don't think it's more "actual" lines of code (I think the wrapping is
>> inflating the line number count),
>
> I too think it doesn't make sense to blow task_struct and the generated code.
> And to me this patch doesn't make the source code more clean.
>
>> but switching it means that it's more in
>> line with other queues in the kernel (it took me a bit to figure out what
>> was going on with oom_reaper_list beforehand).
>
> perhaps you can turn oom_reaper_list into llist_head then. This will also
> allow to remove oom_reaper_lock. Not sure this makes sense too.

Actually, I just noticed that the original implementation is a stack not 
a queue. So the reaper will always reap the *most recent* task to get 
OOMed as opposed to the least recent. Since select_bad_process() will 
always pick worse processes first, this means that the reaper will reap 
"less bad" processes (lower oom score) before it reaps worse ones 
(higher oom score).

While it's not a /huge/ deal (N is going to be small in most OOM cases), 
is this something that we should consider?

RE: llist_head, the problem with that is that appending to the end is an 
O(n) operation. Though, as I said, n is not going to be very large in 
most cases.

-- 
Aleksa Sarai
Software Engineer (Containers)
SUSE Linux GmbH
https://www.cyphar.com/

Re: [PATCH] oom_reaper: switch to struct list_head for reap queue

[Michal Hocko]

On Wed 15-02-17 20:01:33, Aleksa Sarai wrote:
> > > > This is an extra pointer to task_struct and more lines of code to
> > > > accomplish the same thing. Why would we want to do that?
> > > 
> > > I don't think it's more "actual" lines of code (I think the wrapping is
> > > inflating the line number count),
> > 
> > I too think it doesn't make sense to blow task_struct and the generated code.
> > And to me this patch doesn't make the source code more clean.
> > 
> > > but switching it means that it's more in
> > > line with other queues in the kernel (it took me a bit to figure out what
> > > was going on with oom_reaper_list beforehand).
> > 
> > perhaps you can turn oom_reaper_list into llist_head then. This will also
> > allow to remove oom_reaper_lock. Not sure this makes sense too.
> 
> Actually, I just noticed that the original implementation is a stack not a
> queue. So the reaper will always reap the *most recent* task to get OOMed as
> opposed to the least recent. Since select_bad_process() will always pick
> worse processes first, this means that the reaper will reap "less bad"
> processes (lower oom score) before it reaps worse ones (higher oom score).
> 
> While it's not a /huge/ deal (N is going to be small in most OOM cases), is
> this something that we should consider?

Not really. Because the oom killer will back off if there is an oom
victim in the same oom domain currently selected (see
oom_evaluate_task). So more oom tasks queued for the oom reaper will
usually happen when we have parallel OOM in different oom domains
(cpusets/node_masks, memcgs) and then it really doesn't matter which one
we choose first.

-- 
Michal Hocko
SUSE Labs