aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAshwin Chaugule <ashwin.chaugule@celunite.com>2006-12-06 23:31:57 -0500
committerLinus Torvalds <torvalds@woody.osdl.org>2006-12-07 11:39:21 -0500
commit7602bdf2fd14a40dd9b104e516fdc05e1bd17952 (patch)
tree5ca703b0a95f6f2e6d977c816532b9085f453974
parent098fe651f7e9d759d1117c78c1a642b9b3945922 (diff)
[PATCH] new scheme to preempt swap token
The new swap token patches replace the current token traversal algo. The old algo had a crude timeout parameter that was used to handover the token from one task to another. This algo, transfers the token to the tasks that are in need of the token. The urgency for the token is based on the number of times a task is required to swap-in pages. Accordingly, the priority of a task is incremented if it has been badly affected due to swap-outs. To ensure that the token doesnt bounce around rapidly, the token holders are given a priority boost. The priority of tasks is also decremented, if their rate of swap-in's keeps reducing. This way, the condition to check whether to pre-empt the swap token, is a matter of comparing two task's priority fields. [akpm@osdl.org: cleanups] Signed-off-by: Ashwin Chaugule <ashwin.chaugule@celunite.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
-rw-r--r--include/linux/sched.h13
-rw-r--r--include/linux/swap.h1
-rw-r--r--kernel/fork.c8
-rw-r--r--kernel/sysctl.c11
-rw-r--r--mm/thrash.c116
5 files changed, 63 insertions, 86 deletions
diff --git a/include/linux/sched.h b/include/linux/sched.h
index eafe4a7b8237..cad6a16260f7 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -344,9 +344,16 @@ struct mm_struct {
344 /* Architecture-specific MM context */ 344 /* Architecture-specific MM context */
345 mm_context_t context; 345 mm_context_t context;
346 346
347 /* Token based thrashing protection. */ 347 /* Swap token stuff */
348 unsigned long swap_token_time; 348 /*
349 char recent_pagein; 349 * Last value of global fault stamp as seen by this process.
350 * In other words, this value gives an indication of how long
351 * it has been since this task got the token.
352 * Look at mm/thrash.c
353 */
354 unsigned int faultstamp;
355 unsigned int token_priority;
356 unsigned int last_interval;
350 357
351 /* coredumping support */ 358 /* coredumping support */
352 int core_waiters; 359 int core_waiters;
diff --git a/include/linux/swap.h b/include/linux/swap.h
index e7c36ba2a2db..89f8a39773bf 100644
--- a/include/linux/swap.h
+++ b/include/linux/swap.h
@@ -259,7 +259,6 @@ extern spinlock_t swap_lock;
259 259
260/* linux/mm/thrash.c */ 260/* linux/mm/thrash.c */
261extern struct mm_struct * swap_token_mm; 261extern struct mm_struct * swap_token_mm;
262extern unsigned long swap_token_default_timeout;
263extern void grab_swap_token(void); 262extern void grab_swap_token(void);
264extern void __put_swap_token(struct mm_struct *); 263extern void __put_swap_token(struct mm_struct *);
265 264
diff --git a/kernel/fork.c b/kernel/fork.c
index 8cdd3e72ba55..5678e6c61ef2 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -479,6 +479,10 @@ static struct mm_struct *dup_mm(struct task_struct *tsk)
479 479
480 memcpy(mm, oldmm, sizeof(*mm)); 480 memcpy(mm, oldmm, sizeof(*mm));
481 481
482 /* Initializing for Swap token stuff */
483 mm->token_priority = 0;
484 mm->last_interval = 0;
485
482 if (!mm_init(mm)) 486 if (!mm_init(mm))
483 goto fail_nomem; 487 goto fail_nomem;
484 488
@@ -542,6 +546,10 @@ static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)
542 goto fail_nomem; 546 goto fail_nomem;
543 547
544good_mm: 548good_mm:
549 /* Initializing for Swap token stuff */
550 mm->token_priority = 0;
551 mm->last_interval = 0;
552
545 tsk->mm = mm; 553 tsk->mm = mm;
546 tsk->active_mm = mm; 554 tsk->active_mm = mm;
547 return 0; 555 return 0;
diff --git a/kernel/sysctl.c b/kernel/sysctl.c
index 09e569f4792b..7abe9704e75a 100644
--- a/kernel/sysctl.c
+++ b/kernel/sysctl.c
@@ -977,17 +977,6 @@ static ctl_table vm_table[] = {
977 .extra1 = &zero, 977 .extra1 = &zero,
978 }, 978 },
979#endif 979#endif
980#ifdef CONFIG_SWAP
981 {
982 .ctl_name = VM_SWAP_TOKEN_TIMEOUT,
983 .procname = "swap_token_timeout",
984 .data = &swap_token_default_timeout,
985 .maxlen = sizeof(swap_token_default_timeout),
986 .mode = 0644,
987 .proc_handler = &proc_dointvec_jiffies,
988 .strategy = &sysctl_jiffies,
989 },
990#endif
991#ifdef CONFIG_NUMA 980#ifdef CONFIG_NUMA
992 { 981 {
993 .ctl_name = VM_ZONE_RECLAIM_MODE, 982 .ctl_name = VM_ZONE_RECLAIM_MODE,
diff --git a/mm/thrash.c b/mm/thrash.c
index f4c560b4a2b7..19e428ca8b03 100644
--- a/mm/thrash.c
+++ b/mm/thrash.c
@@ -7,100 +7,74 @@
7 * 7 *
8 * Simple token based thrashing protection, using the algorithm 8 * Simple token based thrashing protection, using the algorithm
9 * described in: http://www.cs.wm.edu/~sjiang/token.pdf 9 * described in: http://www.cs.wm.edu/~sjiang/token.pdf
10 *
11 * Sep 2006, Ashwin Chaugule <ashwin.chaugule@celunite.com>
12 * Improved algorithm to pass token:
13 * Each task has a priority which is incremented if it contended
14 * for the token in an interval less than its previous attempt.
15 * If the token is acquired, that task's priority is boosted to prevent
16 * the token from bouncing around too often and to let the task make
17 * some progress in its execution.
10 */ 18 */
19
11#include <linux/jiffies.h> 20#include <linux/jiffies.h>
12#include <linux/mm.h> 21#include <linux/mm.h>
13#include <linux/sched.h> 22#include <linux/sched.h>
14#include <linux/swap.h> 23#include <linux/swap.h>
15 24
16static DEFINE_SPINLOCK(swap_token_lock); 25static DEFINE_SPINLOCK(swap_token_lock);
17static unsigned long swap_token_timeout; 26struct mm_struct *swap_token_mm;
18static unsigned long swap_token_check; 27unsigned int global_faults;
19struct mm_struct * swap_token_mm = &init_mm;
20
21#define SWAP_TOKEN_CHECK_INTERVAL (HZ * 2)
22#define SWAP_TOKEN_TIMEOUT (300 * HZ)
23/*
24 * Currently disabled; Needs further code to work at HZ * 300.
25 */
26unsigned long swap_token_default_timeout = SWAP_TOKEN_TIMEOUT;
27
28/*
29 * Take the token away if the process had no page faults
30 * in the last interval, or if it has held the token for
31 * too long.
32 */
33#define SWAP_TOKEN_ENOUGH_RSS 1
34#define SWAP_TOKEN_TIMED_OUT 2
35static int should_release_swap_token(struct mm_struct *mm)
36{
37 int ret = 0;
38 if (!mm->recent_pagein)
39 ret = SWAP_TOKEN_ENOUGH_RSS;
40 else if (time_after(jiffies, swap_token_timeout))
41 ret = SWAP_TOKEN_TIMED_OUT;
42 mm->recent_pagein = 0;
43 return ret;
44}
45 28
46/*
47 * Try to grab the swapout protection token. We only try to
48 * grab it once every TOKEN_CHECK_INTERVAL, both to prevent
49 * SMP lock contention and to check that the process that held
50 * the token before is no longer thrashing.
51 */
52void grab_swap_token(void) 29void grab_swap_token(void)
53{ 30{
54 struct mm_struct *mm; 31 int current_interval;
55 int reason;
56 32
57 /* We have the token. Let others know we still need it. */ 33 global_faults++;
58 if (has_swap_token(current->mm)) {
59 current->mm->recent_pagein = 1;
60 if (unlikely(!swap_token_default_timeout))
61 disable_swap_token();
62 return;
63 }
64
65 if (time_after(jiffies, swap_token_check)) {
66 34
67 if (!swap_token_default_timeout) { 35 current_interval = global_faults - current->mm->faultstamp;
68 swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
69 return;
70 }
71
72 /* ... or if we recently held the token. */
73 if (time_before(jiffies, current->mm->swap_token_time))
74 return;
75 36
76 if (!spin_trylock(&swap_token_lock)) 37 if (!spin_trylock(&swap_token_lock))
77 return; 38 return;
78 39
79 swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL; 40 /* First come first served */
41 if (swap_token_mm == NULL) {
42 current->mm->token_priority = current->mm->token_priority + 2;
43 swap_token_mm = current->mm;
44 goto out;
45 }
80 46
81 mm = swap_token_mm; 47 if (current->mm != swap_token_mm) {
82 if ((reason = should_release_swap_token(mm))) { 48 if (current_interval < current->mm->last_interval)
83 unsigned long eligible = jiffies; 49 current->mm->token_priority++;
84 if (reason == SWAP_TOKEN_TIMED_OUT) { 50 else {
85 eligible += swap_token_default_timeout; 51 current->mm->token_priority--;
86 } 52 if (unlikely(current->mm->token_priority < 0))
87 mm->swap_token_time = eligible; 53 current->mm->token_priority = 0;
88 swap_token_timeout = jiffies + swap_token_default_timeout; 54 }
55 /* Check if we deserve the token */
56 if (current->mm->token_priority >
57 swap_token_mm->token_priority) {
58 current->mm->token_priority += 2;
89 swap_token_mm = current->mm; 59 swap_token_mm = current->mm;
90 } 60 }
91 spin_unlock(&swap_token_lock); 61 } else {
62 /* Token holder came in again! */
63 current->mm->token_priority += 2;
92 } 64 }
93 return; 65
66out:
67 current->mm->faultstamp = global_faults;
68 current->mm->last_interval = current_interval;
69 spin_unlock(&swap_token_lock);
70return;
94} 71}
95 72
96/* Called on process exit. */ 73/* Called on process exit. */
97void __put_swap_token(struct mm_struct *mm) 74void __put_swap_token(struct mm_struct *mm)
98{ 75{
99 spin_lock(&swap_token_lock); 76 spin_lock(&swap_token_lock);
100 if (likely(mm == swap_token_mm)) { 77 if (likely(mm == swap_token_mm))
101 mm->swap_token_time = jiffies + SWAP_TOKEN_CHECK_INTERVAL; 78 swap_token_mm = NULL;
102 swap_token_mm = &init_mm;
103 swap_token_check = jiffies;
104 }
105 spin_unlock(&swap_token_lock); 79 spin_unlock(&swap_token_lock);
106} 80}