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 {
         /* Architecture-specific MM context */
         mm_context_t context;
 
-        /* Token based thrashing protection. */
-        unsigned long swap_token_time;
-        char recent_pagein;
+        /* Swap token stuff */
+        /*
+         * Last value of global fault stamp as seen by this process.
+         * In other words, this value gives an indication of how long
+         * it has been since this task got the token.
+         * Look at mm/thrash.c
+         */
+        unsigned int faultstamp;
+        unsigned int token_priority;
+        unsigned int last_interval;
 
         /* coredumping support */
         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;
 
 /* linux/mm/thrash.c */
 extern struct mm_struct * swap_token_mm;
-extern unsigned long swap_token_default_timeout;
 extern void grab_swap_token(void);
 extern void __put_swap_token(struct mm_struct *);
 
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)
 
         memcpy(mm, oldmm, sizeof(*mm));
 
+        /* Initializing for Swap token stuff */
+        mm->token_priority = 0;
+        mm->last_interval = 0;
+
         if (!mm_init(mm))
                 goto fail_nomem;
 
@@ -542,6 +546,10 @@ static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)
                 goto fail_nomem;
 
 good_mm:
+        /* Initializing for Swap token stuff */
+        mm->token_priority = 0;
+        mm->last_interval = 0;
+
         tsk->mm = mm;
         tsk->active_mm = mm;
         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[] = {
                 .extra1         = &zero,
         },
 #endif
-#ifdef CONFIG_SWAP
-        {
-                .ctl_name       = VM_SWAP_TOKEN_TIMEOUT,
-                .procname       = "swap_token_timeout",
-                .data           = &swap_token_default_timeout,
-                .maxlen         = sizeof(swap_token_default_timeout),
-                .mode           = 0644,
-                .proc_handler   = &proc_dointvec_jiffies,
-                .strategy       = &sysctl_jiffies,
-        },
-#endif
 #ifdef CONFIG_NUMA
         {
                 .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 @@
  *
  * Simple token based thrashing protection, using the algorithm
  * described in:  http://www.cs.wm.edu/~sjiang/token.pdf
+ *
+ * Sep 2006, Ashwin Chaugule <ashwin.chaugule@celunite.com>
+ * Improved algorithm to pass token:
+ * Each task has a priority which is incremented if it contended
+ * for the token in an interval less than its previous attempt.
+ * If the token is acquired, that task's priority is boosted to prevent
+ * the token from bouncing around too often and to let the task make
+ * some progress in its execution.
  */
+
 #include <linux/jiffies.h>
 #include <linux/mm.h>
 #include <linux/sched.h>
 #include <linux/swap.h>
 
 static DEFINE_SPINLOCK(swap_token_lock);
-static unsigned long swap_token_timeout;
-static unsigned long swap_token_check;
-struct mm_struct * swap_token_mm = &init_mm;
-
-#define SWAP_TOKEN_CHECK_INTERVAL (HZ * 2)
-#define SWAP_TOKEN_TIMEOUT      (300 * HZ)
-/*
- * Currently disabled; Needs further code to work at HZ * 300.
- */
-unsigned long swap_token_default_timeout = SWAP_TOKEN_TIMEOUT;
-
-/*
- * Take the token away if the process had no page faults
- * in the last interval, or if it has held the token for
- * too long.
- */
-#define SWAP_TOKEN_ENOUGH_RSS 1
-#define SWAP_TOKEN_TIMED_OUT 2
-static int should_release_swap_token(struct mm_struct *mm)
-{
-        int ret = 0;
-        if (!mm->recent_pagein)
-                ret = SWAP_TOKEN_ENOUGH_RSS;
-        else if (time_after(jiffies, swap_token_timeout))
-                ret = SWAP_TOKEN_TIMED_OUT;
-        mm->recent_pagein = 0;
-        return ret;
-}
+struct mm_struct *swap_token_mm;
+unsigned int global_faults;
 
-/*
- * Try to grab the swapout protection token.  We only try to
- * grab it once every TOKEN_CHECK_INTERVAL, both to prevent
- * SMP lock contention and to check that the process that held
- * the token before is no longer thrashing.
- */
 void grab_swap_token(void)
 {
-        struct mm_struct *mm;
-        int reason;
+        int current_interval;
 
-        /* We have the token. Let others know we still need it. */
-        if (has_swap_token(current->mm)) {
-                current->mm->recent_pagein = 1;
-                if (unlikely(!swap_token_default_timeout))
-                        disable_swap_token();
-                return;
-        }
-
-        if (time_after(jiffies, swap_token_check)) {
+        global_faults++;
 
-                if (!swap_token_default_timeout) {
-                        swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
-                        return;
-                }
-
-                /* ... or if we recently held the token. */
-                if (time_before(jiffies, current->mm->swap_token_time))
-                        return;
+        current_interval = global_faults - current->mm->faultstamp;
 
-                if (!spin_trylock(&swap_token_lock))
-                        return;
+        if (!spin_trylock(&swap_token_lock))
+                return;
 
-                swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
+        /* First come first served */
+        if (swap_token_mm == NULL) {
+                current->mm->token_priority = current->mm->token_priority + 2;
+                swap_token_mm = current->mm;
+                goto out;
+        }
 
-                mm = swap_token_mm;
-                if ((reason = should_release_swap_token(mm))) {
-                        unsigned long eligible = jiffies;
-                        if (reason == SWAP_TOKEN_TIMED_OUT) {
-                                eligible += swap_token_default_timeout;
-                        }
-                        mm->swap_token_time = eligible;
-                        swap_token_timeout = jiffies + swap_token_default_timeout;
+        if (current->mm != swap_token_mm) {
+                if (current_interval < current->mm->last_interval)
+                        current->mm->token_priority++;
+                else {
+                        current->mm->token_priority--;
+                        if (unlikely(current->mm->token_priority < 0))
+                                current->mm->token_priority = 0;
+                }
+                /* Check if we deserve the token */
+                if (current->mm->token_priority >
+                                swap_token_mm->token_priority) {
+                        current->mm->token_priority += 2;
                         swap_token_mm = current->mm;
                 }
-                spin_unlock(&swap_token_lock);
+        } else {
+                /* Token holder came in again! */
+                current->mm->token_priority += 2;
         }
-        return;
+
+out:
+        current->mm->faultstamp = global_faults;
+        current->mm->last_interval = current_interval;
+        spin_unlock(&swap_token_lock);
+return;
 }
 
 /* Called on process exit. */
 void __put_swap_token(struct mm_struct *mm)
 {
         spin_lock(&swap_token_lock);
-        if (likely(mm == swap_token_mm)) {
-                mm->swap_token_time = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
-                swap_token_mm = &init_mm;
-                swap_token_check = jiffies;
-        }
+        if (likely(mm == swap_token_mm))
+                swap_token_mm = NULL;
         spin_unlock(&swap_token_lock);
 }