LCA OOM-Killer v2.3

PATCH New Coywolf Qi Hunt 1 participant 1 message May 14, 2005

Subsystems (7)

Memory management MM core Scheduler exec and binfmt +3 more subsystems

lore

Share & tools

lore

Coywolf Qi Hunt

author

2005-05-14 19:56 UTC #0 lore raw

PATCH 1/1 LCA OOM-Killer v2.3

Coywolf Qi Hunt
[email protected]
May 14, 2005

LCA OOM-Killer v2.3

1. Acronyms

OOM Out of Memory
LCA Least Common Ancestor

2. Introduction

The traditional solutions to fork bombs, such as ulimit are limited in usability and functionality. If you put a cap on the resource limit to N, your system could always be able to afford N+1. Consider multiple logging's, you can not prevent attacks by simply using a resource limit. And you can not easily prevent root fork bombs.

3. Philosophy

Kernel is God, init is Jesus. Init could be /sbin/init or /bin/sh - whatsoever we've chosen. So the kernel protects only the init process, not root processes, or other things.

If we follow the UNIX philosophy that allow root to shoot his own foot, then we could protect root processes and kill other processes by user. Someone had advised me to kill on a per user basis. We could do that, but I think that is doing revenge. For instance, from tty1 one does normal work, but from tty2, I runs fork bomb. The kernel should only kill the bomb from tty2.

The LCA algorithm is to find out the malicious process, not the malicious user. Leave that job to system admins, not the kernel.

4. Three Working Levels

level 0

Conservative level. last_chosen_parent will be forgotten after lca_time seconds. System could be "choking" periodically. The caught isn't guaranteed, but computing could still going on.

level 1

Modest level. last_chosen_parent is used only if it's younger than 1<<lca_time++ seconds. And the more hits, the longer(exponential) it will be memorized. Some fork bombs could do fork bombings by their descendents. But they'll be caught sooner or later if they keep misbehaving. At the beginning, level 2 works as level 1 in effect. If fork bombing keeps happening, level 2 will be acting like level 3. The caught is guaranteed in level 2.

level 2

Strong, fierce level. No expiration for last_chosen_parent. Thus any fork bombs will be caught and killed immediately. But innocents could be mass killed.

5. Interfaces

	The sysctls and their default values:

	/proc/sys/vm/lca_level		0
	/proc/sys/vm/lca_time		5

6. Overhead Considerations

It's one pointer and two list_head structures added to task_struct, exactly as ptrace. Few users use ptrace, so ptrace is somewhat depreciated?

Would you really care about 20 bytes for each process? I usually have no more than 70 processes. That is 70 * 20 = 1400 bytes for me. Every 204 processes use up roughly one page of memory.

In v1.0, only one pointer is added. So the overhead is 4 bytes per process. But then find_lca() and the descendant killing have to be O(n^2). That's not acceptable.

We might even be able to avoid the 20 bytes overhead by some heavy hacking or not trying to be strict POSIX compliant on this part. In this case, nearly no overhead at all.

7. Other Considerations

1. The patch works as well as its previous release upon the normal test cases (a.sh, b.sh, c.sh and folkert). With swapon, it will take longer time to trigger the OOM by kernel itself at present. (I have other plans to improve it...)

In addition to the 4 normal test cases, there are two ``pure'' fork bomb cases (canonical and pl.sh). In pure fork bombing cases (just fork, no malloc), it will take longer time to trigger or often will not trigger the OOM by kernel itself at present.

Here goes the bad news that the algorithm cannot deal with pure fork bombs for now (probably not in future either). But the good news is that pure fork bombs are not fatal to the system. The normal users will get messages like "fork resources temporarily unavailable". But root can still continue to work. In my tests, although the system responds slowly, I can still use vi as root.

As an LWN editorial says, this algorithm could be a "last line of defense".

2. Direct hardware access processes and other important processes could be protected by /proc/<pid>/oom_adj.

8. FYI

LCA OOM-killer previous releases

      v2.1 http://lwn.net/Articles/129286/ 
      v2.2 http://lwn.net/Articles/134388/

Defending against fork bombs

      http://lwn.net/Articles/134513/

Test cases
http://freeforge.net/~coywolf/pub/oom-bomb/

Signed-off-by Coywolf Qi Hunt <[email protected]>

---

 fs/proc/base.c            |    3 
 include/linux/init_task.h |    3 
 include/linux/oom_kill.h  |   18 ++++
 include/linux/sched.h     |    9 --
 include/linux/sysctl.h    |    2 
 kernel/exit.c             |   31 ++++++
 kernel/fork.c             |    4 
 kernel/sysctl.c           |   22 ++++
 mm/oom_kill.c             |  205 +++++++++++++++++++++++++++++++++-------------
 9 files changed, 232 insertions(+), 65 deletions(-)

fs/proc/base.c +1 -2

diff -pruN 2.6.12-rc4-mm1/fs/proc/base.c 2.6.12-rc4-mm1-cy/fs/proc/base.c
@@ -69,6 +69,7 @@
 #include <linux/seccomp.h>
 #include <linux/cpuset.h>
 #include <linux/audit.h>
+#include <linux/oom_kill.h>
 #include "internal.h"
 
 /*

@@ -469,8 +470,6 @@ static int proc_pid_schedstat(struct tas
 }
 #endif
 
-/* The badness from the OOM killer */
-unsigned long badness(struct task_struct *p, unsigned long uptime);
 static int proc_oom_score(struct task_struct *task, char *buffer)
 {
 	unsigned long points;

include/linux/init_task.h +3 -0

diff -pruN 2.6.12-rc4-mm1/include/linux/init_task.h 2.6.12-rc4-mm1-cy/include/linux/init_task.h
@@ -90,6 +90,9 @@ extern struct group_info init_groups;
 	.parent		= &tsk,						\
 	.children	= LIST_HEAD_INIT(tsk.children),			\
 	.sibling	= LIST_HEAD_INIT(tsk.sibling),			\
+	.bio_parent	= &tsk,						\
+	.bio_children	= LIST_HEAD_INIT(tsk.bio_children),		\
+	.bio_sibling	= LIST_HEAD_INIT(tsk.bio_sibling),		\
 	.group_leader	= &tsk,						\
 	.group_info	= &init_groups,					\
 	.cap_effective	= CAP_INIT_EFF_SET,				\

include/linux/oom_kill.h +18 -0

diff -pruN 2.6.12-rc4-mm1/include/linux/oom_kill.h 2.6.12-rc4-mm1-cy/include/linux/oom_kill.h
@@ -0,0 +1,18 @@
+/*
+ * include/linux/oom_kill.h
+ *
+ * LCA OOM-killer Header
+ * Copyright (C)  2005.5.9  Coywolf Qi Hunt
+ */
+
+#ifndef _LINUX_OOM_KILL_H
+#define _LINUX_OOM_KILL_H
+
+extern unsigned int lca_level;
+extern unsigned int lca_time;
+extern spinlock_t last_chosen_parent_lock;
+extern struct task_struct *last_chosen_parent;
+
+unsigned long badness(struct task_struct *p, unsigned long uptime);
+
+#endif /* _LINUX_OOM_KILL_H */

include/linux/sched.h +4 -5

diff -pruN 2.6.12-rc4-mm1/include/linux/sched.h 2.6.12-rc4-mm1-cy/include/linux/sched.h
@@ -663,11 +663,7 @@ struct task_struct {
 	unsigned did_exec:1;
 	pid_t pid;
 	pid_t tgid;
-	/* 
-	 * pointers to (original) parent process, youngest child, younger sibling,
-	 * older sibling, respectively.  (p->father can be replaced with 
-	 * p->parent->pid)
-	 */
+
 	struct task_struct *real_parent; /* real parent process (when being debugged) */
 	struct task_struct *parent;	/* parent process */
 	/*

@@ -676,6 +672,9 @@ struct task_struct {
 	 */
 	struct list_head children;	/* list of my children */
 	struct list_head sibling;	/* linkage in my parent's children list */
+	struct task_struct *bio_parent;	/* biological parent process */
+	struct list_head bio_children;
+	struct list_head bio_sibling;
 	struct task_struct *group_leader;	/* threadgroup leader */
 
 	/* PID/PID hash table linkage. */

include/linux/sysctl.h +2 -0

diff -pruN 2.6.12-rc4-mm1/include/linux/sysctl.h 2.6.12-rc4-mm1-cy/include/linux/sysctl.h
@@ -171,6 +171,8 @@ enum
 	VM_VFS_CACHE_PRESSURE=26, /* dcache/icache reclaim pressure */
 	VM_LEGACY_VA_LAYOUT=27, /* legacy/compatibility virtual address space layout */
 	VM_SWAP_TOKEN_TIMEOUT=28, /* default time for token time out */
+	VM_LCA_LEVEL	 = 29,	/* LCA oom-killer work level */
+	VM_LCA_TIME	 = 30,	/* for last_chosen_parent time out */
 };

kernel/exit.c +27 -4

diff -pruN 2.6.12-rc4-mm1/kernel/exit.c 2.6.12-rc4-mm1-cy/kernel/exit.c
@@ -29,6 +29,7 @@
 #include <linux/perfctr.h>
 #include <linux/syscalls.h>
 #include <linux/signal.h>
+#include <linux/oom_kill.h>
 
 #include <asm/uaccess.h>
 #include <asm/unistd.h>

@@ -55,6 +56,7 @@ static void __unhash_process(struct task
 	}
 
 	REMOVE_LINKS(p);
+	list_del_init(&p->bio_sibling);
 }
 
 void release_task(struct task_struct * p)

@@ -224,6 +226,9 @@ static inline int has_stopped_jobs(int p
  * been inherited from a user process, so we reset them to sane values here.
  *
  * NOTE that reparent_to_init() gives the caller full capabilities.
+ *
+ * We change kernel threads' current->bio_*, thus find_lca()
+ * will not catch it.  -- coywolf
  */
 static inline void reparent_to_init(void)
 {

@@ -235,6 +240,9 @@ static inline void reparent_to_init(void
 	current->parent = child_reaper;
 	current->real_parent = child_reaper;
 	SET_LINKS(current);
+	list_del_init(&current->bio_sibling);
+	current->bio_parent = child_reaper;
+	list_add_tail(&current->bio_sibling, &child_reaper->bio_children);
 
 	/* Set the exit signal to SIGCHLD so we signal init on exit */
 	current->exit_signal = SIGCHLD;

@@ -514,7 +522,7 @@ static void exit_mm(struct task_struct *
 	mmput(mm);
 }
 
-static inline void choose_new_parent(task_t *p, task_t *reaper, task_t *child_reaper)
+static inline void choose_new_parent(task_t *p, task_t *reaper)
 {
 	/*
 	 * Make sure we're not reparenting to ourselves and that

@@ -611,7 +619,7 @@ static inline void forget_original_paren
 	 * Search them and reparent children.
 	 */
 	list_for_each_safe(_p, _n, &father->children) {
-		int ptrace;
+		long ptrace;
 		p = list_entry(_p,struct task_struct,sibling);
 
 		ptrace = p->ptrace;

@@ -621,7 +629,7 @@ static inline void forget_original_paren
 
 		if (father == p->real_parent) {
 			/* reparent with a reaper, real father it's us */
-			choose_new_parent(p, reaper, child_reaper);
+			choose_new_parent(p, reaper);
 			reparent_thread(p, father, 0);
 		} else {
 			/* reparent ptraced task to its real parent */

@@ -642,9 +650,24 @@ static inline void forget_original_paren
 	}
 	list_for_each_safe(_p, _n, &father->ptrace_children) {
 		p = list_entry(_p,struct task_struct,ptrace_list);
-		choose_new_parent(p, reaper, child_reaper);
+		choose_new_parent(p, reaper);
 		reparent_thread(p, father, 1);
 	}
+
+	list_for_each_safe(_p, _n,  &father->bio_children) {
+		p = list_entry(_p, struct task_struct, bio_sibling);
+		list_del_init(&p->bio_sibling);
+		p->bio_parent = father->bio_parent;
+		list_add_tail(&p->bio_sibling, &(p->bio_parent)->bio_children);
+	}
+
+	spin_lock(&last_chosen_parent_lock);
+	if (unlikely(father == last_chosen_parent)) {
+		last_chosen_parent = father->bio_parent;
+		if (last_chosen_parent->pid == 1)
+			last_chosen_parent = NULL;
+	}
+	spin_unlock(&last_chosen_parent_lock);
 }
 
 /*

kernel/fork.c +4 -0

diff -pruN 2.6.12-rc4-mm1/kernel/fork.c 2.6.12-rc4-mm1-cy/kernel/fork.c
@@ -914,6 +914,8 @@ static task_t *copy_process(unsigned lon
 
 	INIT_LIST_HEAD(&p->children);
 	INIT_LIST_HEAD(&p->sibling);
+	INIT_LIST_HEAD(&p->bio_children);
+	INIT_LIST_HEAD(&p->bio_sibling);
 	p->vfork_done = NULL;
 	spin_lock_init(&p->alloc_lock);
 	spin_lock_init(&p->proc_lock);

@@ -1046,6 +1048,7 @@ static task_t *copy_process(unsigned lon
 	else
 		p->real_parent = current;
 	p->parent = p->real_parent;
+	p->bio_parent = current;
 
 	if (clone_flags & CLONE_THREAD) {
 		spin_lock(&current->sighand->siglock);

@@ -1096,6 +1099,7 @@ static task_t *copy_process(unsigned lon
 	p->ioprio = current->ioprio;
 
 	SET_LINKS(p);
+	list_add_tail(&p->bio_sibling, &current->bio_children);
 	if (unlikely(p->ptrace & PT_PTRACED))
 		__ptrace_link(p, current->parent);

kernel/sysctl.c +22 -0

diff -pruN 2.6.12-rc4-mm1/kernel/sysctl.c 2.6.12-rc4-mm1-cy/kernel/sysctl.c
@@ -41,6 +41,7 @@
 #include <linux/limits.h>
 #include <linux/dcache.h>
 #include <linux/syscalls.h>
+#include <linux/oom_kill.h>
 
 #include <asm/uaccess.h>
 #include <asm/processor.h>

@@ -650,6 +651,7 @@ static ctl_table kern_table[] = {
 /* Constants for minimum and maximum testing in vm_table.
    We use these as one-element integer vectors. */
 static int zero;
+static int two = 2;
 static int one_hundred = 100;

@@ -837,6 +839,26 @@ static ctl_table vm_table[] = {
 		.strategy	= &sysctl_jiffies,
 	},
 #endif
+	{
+		.ctl_name	= VM_LCA_LEVEL,
+		.procname	= "lca_level",
+		.data		= &lca_level,
+		.maxlen		= sizeof(lca_level),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &zero,
+		.extra2		= &two,
+	},
+	{
+		.ctl_name	= VM_LCA_TIME,
+		.procname	= "lca_time",
+		.data		= &lca_time,
+		.maxlen		= sizeof(lca_time),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+		.strategy	= &sysctl_intvec,
+	},
 	{ .ctl_name = 0 }
 };

mm/oom_kill.c +151 ~~-54~~

310 lines not on this page · raw message