Skip to contentSkip to conversation

oom lca -- fork bombing killer

PATCH In review Coywolf Qi Hunt 3 participants 3 messages Mar 28, 2005 – Mar 31, 2005

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 oom lca -- fork bombing killer

March 28, 2005
Coywolf Qi Hunt
[email protected]

Linux OOM LCA (Least Common Ancestor) Patch

An anti Fork Bombing Solution

Introduction

People complain that linux is still vulnerable to the ancient fork bombing. A quick scratch <http://freeforge.net/~coywolf/oom-bomb/> simply running as normal user could make a linux box totally unusable.

Another example is in the recent thread: oom with 2.6.11
<http://lkml.org/lkml/2005/3/17/142>

The only way currently to deal with fork bombing is to limit the number of running processes or the forking rate. This patch brings a new way to find out and kill the possible fork bombing processes or any misbehaving processes taking up too much memory.

The patch applies to 2.6.12-rc1-mm3 and seems able to kill various fork bombings.

Simple Experiment Result

It is tested on an 256M desktop box. With swapoff and in console, it works pretty well. After the fork bomber has forked into about 1500 instances,

	RES = 1036k
	SHR = 876k
	1500*(1036k-876k)=234M

it got killed completely.

When the fork bomber is running as root, kernel first kills the X server and XFce4 el al, immediately kernel kills the bomb totally too.

I haven't tested with swapon yet. The hard disk would keep swapping badly then.

When in X, the screen got corrupted, but the box can still reboot through ctrl+alt+del.

The oom LCA algorithm details

1. New elements add to struct task_struct :
struct task_struct *bio_parent
struct list_head bio_children;
struct list_head bio_sibling;

Adds struct task_struct *bio_parent to struct task_struct. Unlike struct task_struct *parent, user programs can not change it by daemon(3). It is describing the facts except when it is a kernel thread. We don't plan to oom kill any kernel threads.

2. If a process is malicious, we'll consider its children malicious too. So we kill the choose process and all its descendants. This way we'll be far faster than the tumor forking. LCA always grows upwards.

3. LCA(Least Common Ancestor Algorithm, I choose the term LCA for it is more widely used than NCA(Nearest Common Ancestor) according to google.) We remember the last killed process' parent, next time we'll kill the remembered last_chosen_parent and the new worst process(the highest badness)'s least common ancestor. NOTE if find_lca() fails, we just kill the worst process and we must _update_ the last_kill_process to a new value.

4. Calculates oom badness
bio_children is considered instead of children.

Not quite related changes

I also include some other obvious cleanups. They are:

1. hides reparent_to_init(), reparent_to_init() should be called only by daemonize()
2. removes obsolete code comments in task_struct
3. removes an obsolete parameter from choose_new_parent() and cleanups
4. in reparent_thread(), ptrace should be type long, not int.
5. cleanups in mm/oom_kill.c

---

 arch/i386/mach-voyager/voyager_thread.c |    1 
 include/linux/init_task.h               |    3 
 include/linux/sched.h                   |   10 --
 kernel/exit.c                           |   34 ++++++-
 kernel/fork.c                           |    4 
 mm/oom_kill.c                           |  141 ++++++++++++++++++++------------
 6 files changed, 129 insertions(+), 64 deletions(-)
arch/i386/mach-voyager/voyager_thread.c +0 -1
diff -pruN 2.6.12-rc1-mm3/arch/i386/mach-voyager/voyager_thread.c 2.6.12-rc1-mm3-cy/arch/i386/mach-voyager/voyager_thread.c
@@ -126,7 +126,6 @@ thread(void *unused)
 
 	kvoyagerd_running = 1;
 
-	reparent_to_init();
 	daemonize(THREAD_NAME);
 
 	set_timeout = 0;
include/linux/init_task.h +3 -0
diff -pruN 2.6.12-rc1-mm3/include/linux/init_task.h 2.6.12-rc1-mm3-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/sched.h +4 -6
diff -pruN 2.6.12-rc1-mm3/include/linux/sched.h 2.6.12-rc1-mm3-cy/include/linux/sched.h
@@ -656,11 +656,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 */
 	/*
@@ -669,6 +665,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;	
+	struct list_head bio_children;
+	struct list_head bio_sibling;
 	struct task_struct *group_leader;	/* threadgroup leader */
 
 	/* PID/PID hash table linkage. */
@@ -1068,7 +1067,6 @@ extern void exit_itimers(struct signal_s
 
 extern NORET_TYPE void do_group_exit(int);
 
-extern void reparent_to_init(void);
 extern void daemonize(const char *, ...);
 extern int allow_signal(int);
 extern int disallow_signal(int);
kernel/exit.c +27 -7
diff -pruN 2.6.12-rc1-mm3/kernel/exit.c 2.6.12-rc1-mm3-cy/kernel/exit.c
@@ -52,6 +52,7 @@ static void __unhash_process(struct task
 	}
 
 	REMOVE_LINKS(p);
+	list_del_init(&p->bio_sibling);
 }
 
 void release_task(struct task_struct * p)
@@ -221,8 +222,11 @@ 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
  */
-void reparent_to_init(void)
+static inline void reparent_to_init(void)
 {
 	write_lock_irq(&tasklist_lock);
 
@@ -232,6 +236,9 @@ 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;
@@ -511,16 +518,15 @@ void exit_mm(struct task_struct * tsk)
 	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
 	 * the parent is not a zombie.
 	 */
 	BUG_ON(p == reaper || reaper->exit_state >= EXIT_ZOMBIE);
+	BUG_ON(p->parent == reaper);
 	p->real_parent = reaper;
-	if (p->parent == p->real_parent)
-		BUG();
 }
 
 static inline void reparent_thread(task_t *p, task_t *father, int traced)
@@ -590,6 +596,7 @@ static inline void reparent_thread(task_
 static inline void forget_original_parent(struct task_struct * father,
 					  struct list_head *to_release)
 {
+	extern struct task_struct *last_chosen_parent;
 	struct task_struct *p, *reaper = father;
 	struct list_head *_p, *_n;
 
@@ -610,7 +617,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;
@@ -620,7 +627,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 */
@@ -641,9 +648,22 @@ 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);
+	}
+
+	if (unlikely(father == last_chosen_parent)) {
+		last_chosen_parent = father->bio_parent;
+		if (last_chosen_parent == &init_task)
+			last_chosen_parent = NULL;
+	}
 }
 
 /*
kernel/fork.c +4 -0
diff -pruN 2.6.12-rc1-mm3/kernel/fork.c 2.6.12-rc1-mm3-cy/kernel/fork.c
@@ -915,6 +915,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);
@@ -1044,6 +1046,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);
@@ -1094,6 +1097,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);
 
mm/oom_kill.c +91 -50

225 lines not on this page · raw message

#1 lore raw
Quoted 22 lines · Coywolf Qi Hunt

Linux OOM LCA (Least Common Ancestor) Patch

...

include/linux/sched.h +1 -5
@@ -656,11 +656,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 */
 	/*

include/linux/sched.h struct task_struct { · line 673

Quoted 9 lines
include/linux/sched.h +3 -0
@@ -669,6 +665,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;	
+	struct list_head bio_children;
+	struct list_head bio_sibling;
 	struct task_struct *group_leader;	/* threadgroup leader */
 
 	/* PID/PID hash table linkage. */

Well that was a bit cruel - it would have been better to fix up the comment rather than deleting it. And to have documented the newly-added fields.

(The bio_* names remind me of fs/bio.c. Maybe rename them to initial_*?)

include/linux/sched.h extern void exit_itimers(struct signal_s · line 1071

Quoted 5 lines
include/linux/sched.h +0 -1
@@ -1068,7 +1067,6 @@ extern void exit_itimers(struct signal_s
 
 extern NORET_TYPE void do_group_exit(int);
 
-extern void reparent_to_init(void);

OK, but the reparent_to_init() cleanup should be a separate patch, please.

include/linux/sched.h static inline void reparent_thread(task_ · line 599

Quoted 6 lines
include/linux/sched.h +1 -0
 static inline void reparent_thread(task_t *p, task_t *father, int traced)
@@ -590,6 +596,7 @@ static inline void reparent_thread(task_
 static inline void forget_original_parent(struct task_struct * father,
 					  struct list_head *to_release)
 {
+	extern struct task_struct *last_chosen_parent;

This declaration should be in a header file.

include/linux/sched.h static inline void reparent_thread(task_

Quoted 7 lines
include/linux/sched.h +7 -0
+
+	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);
+	}

This big list walk on the exit path might be unpopular from a performance and latency POV.

Quoted 8 lines

/*
+ * LCA: Least Common Ancestor
+ *
+ * Returns NULL if no LCA (LCA is init_task)
+ *
+ * I prefer to use task_t for function parameters, and
+ * struct task_struct elsewhere. -- coywolf
+ */

Most other people prefer to not use the typedef...

include/linux/sched.h

Quoted 12 lines
include/linux/sched.h +12 -0
+static struct task_struct * find_lca(task_t *p1, task_t *p2)
+{
+	struct task_struct *tsk1, *tsk2;
+
+	for (tsk1 = p1; tsk1 != &init_task; tsk1 = tsk1->bio_parent) {
+		for (tsk2 = p2; tsk2 != &init_task; tsk2 = tsk2->bio_parent)
+			if (tsk1 == tsk2)
+				return tsk1;
+	}
+
+	return NULL;
+}

eep. That's an O(n^2) search? What does it do with 50000 tasks?

Quoted 16 lines
include/linux/sched.h +5 -10
-	struct task_struct *c;
-	struct list_head *tsk;
+	if (list_empty(&p->bio_children)) {
+		mmput(mm);
+		__oom_kill_task(p);
+		return 1;
+	}
 
-	/* Try to kill a child first */
-	list_for_each(tsk, &p->children) {
-		c = list_entry(tsk, struct task_struct, sibling);
-		if (c->mm == p->mm)
-			continue;
-		mm = oom_kill_task(c);
-		if (mm)
-			return mm;

include/linux/sched.h

Quoted 10 lines
include/linux/sched.h +9 -0
+	/* Kill all descendants */
+	for_each_process(q) {
+		if (q->pid > 1) {
+			if (test_tsk_thread_flag(q, TIF_MEMDIE) ||
+				(q->flags & PF_EXITING) || (q->flags & PF_DEAD))
+				continue;
+			if (is_ancestor(p, q))
+				__oom_kill_task(q);
+		}
 	}

That's O(n^2) too.

#2 lore raw
Quoted 31 lines · Andrew Morton
Quoted 29 lines · Coywolf Qi Hunt

Linux OOM LCA (Least Common Ancestor) Patch

...

include/linux/sched.h +4 -5
@@ -656,11 +656,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 */
 	/*
@@ -669,6 +665,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;	
+	struct list_head bio_children;
+	struct list_head bio_sibling;
 	struct task_struct *group_leader;	/* threadgroup leader */
 
Quoted 5 lines

include/linux/sched.h struct task_struct { · line 673

Quoted 1 line
include/linux/sched.h +0 -0
 	/* PID/PID hash table linkage. */

Well that was a bit cruel - it would have been better to fix up the comment rather than deleting it. And to have documented the newly-added fields.

There used to have struct task_struct *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr; They've all disappeared in 2.6. That comment is about that.

Quoted 2 lines

(The bio_* names remind me of fs/bio.c. Maybe rename them to initial_*?)

biological parent, bio_parent. It makes sense, so basically.

Quoted 24 lines

include/linux/sched.h extern void exit_itimers(struct signal_s · line 1071

Quoted 8 lines
include/linux/sched.h +0 -1
@@ -1068,7 +1067,6 @@ extern void exit_itimers(struct signal_s
 
 extern NORET_TYPE void do_group_exit(int);
 
-extern void reparent_to_init(void);

OK, but the reparent_to_init() cleanup should be a separate patch, please.

include/linux/sched.h static inline void reparent_thread(task_ · line 599

Quoted 6 lines
include/linux/sched.h +1 -0
 static inline void reparent_thread(task_t *p, task_t *father, int traced)
@@ -590,6 +596,7 @@ static inline void reparent_thread(task_
 static inline void forget_original_parent(struct task_struct * father,
 					  struct list_head *to_release)
 {
+	extern struct task_struct *last_chosen_parent;

This declaration should be in a header file.

Quoted 11 lines

include/linux/sched.h static inline void reparent_thread(task_

Quoted 7 lines
include/linux/sched.h +7 -0
+
+	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);
+	}

This big list walk on the exit path might be unpopular from a performance and latency POV.

There are already two other list walks. This one isn't much bigger.
It's unavoidable in normal process exits. But it could be avoided during oom killing by always killing leaves.

Quoted 15 lines
Quoted 10 lines

/*
+ * LCA: Least Common Ancestor
+ *
+ * Returns NULL if no LCA (LCA is init_task)
+ *
+ * I prefer to use task_t for function parameters, and
+ * struct task_struct elsewhere. -- coywolf
+ */

Most other people prefer to not use the typedef...

Quoted 15 lines

include/linux/sched.h

Quoted 12 lines
include/linux/sched.h +12 -0
+static struct task_struct * find_lca(task_t *p1, task_t *p2)
+{
+	struct task_struct *tsk1, *tsk2;
+
+	for (tsk1 = p1; tsk1 != &init_task; tsk1 = tsk1->bio_parent) {
+		for (tsk2 = p2; tsk2 != &init_task; tsk2 = tsk2->bio_parent)
+			if (tsk1 == tsk2)
+				return tsk1;
+	}
+
+	return NULL;
+}

eep. That's an O(n^2) search? What does it do with 50000 tasks?

Two levels 50000 loops cost 4.6 seconds on my 2.4G celeron. Yes, I'll improve it to O(n).

Quoted 23 lines
Quoted 23 lines
include/linux/sched.h +10 -10
-	struct task_struct *c;
-	struct list_head *tsk;
+	if (list_empty(&p->bio_children)) {
+		mmput(mm);
+		__oom_kill_task(p);
+		return 1;
+	}
 
-	/* Try to kill a child first */
-	list_for_each(tsk, &p->children) {
-		c = list_entry(tsk, struct task_struct, sibling);
-		if (c->mm == p->mm)
-			continue;
-		mm = oom_kill_task(c);
-		if (mm)
-			return mm;
+	/* Kill all descendants */
+	for_each_process(q) {
+		if (q->pid > 1) {
+			if (test_tsk_thread_flag(q, TIF_MEMDIE) ||
+				(q->flags & PF_EXITING) || (q->flags & PF_DEAD))
Quoted 9 lines
Quoted 5 lines
include/linux/sched.h +4 -0
+				continue;
+			if (is_ancestor(p, q))
+				__oom_kill_task(q);
+		}
	}

That's O(n^2) too.

I'm working on it. It'll be O(n), and no extra memory allocations even.

The biggest problem is when swapping is on, it doesn't help much. Swapping needs similiar control too. Let's do things one by one.

Coywolf