mm/thrash.c

   1 /*
   2  * mm/thrash.c
   3  *
   4  * Copyright (C) 2004, Red Hat, Inc.
   5  * Copyright (C) 2004, Rik van Riel <riel@redhat.com>
   6  * Released under the GPL, see the file COPYING for details.
   7  *
   8  * Simple token based thrashing protection, using the algorithm
   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.
  18  */
  19
  20 #include <linux/jiffies.h>
  21 #include <linux/mm.h>
  22 #include <linux/sched.h>
  23 #include <linux/swap.h>
  24
  25 static DEFINE_SPINLOCK(swap_token_lock);
  26 struct mm_struct *swap_token_mm;
  27 static unsigned int global_faults;
  28
  29 void grab_swap_token(void)
  30 {
  31         int current_interval;
  32
  33         global_faults++;
  34
  35         current_interval = global_faults - current->mm->faultstamp;
  36
  37         if (!spin_trylock(&swap_token_lock))
  38                 return;
  39
  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         }
  46
  47         if (current->mm != swap_token_mm) {
  48                 if (current_interval < current->mm->last_interval)
  49                         current->mm->token_priority++;
  50                 else {
  51                         current->mm->token_priority--;
  52                         if (unlikely(current->mm->token_priority < 0))
  53                                 current->mm->token_priority = 0;
  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;
  59                         swap_token_mm = current->mm;
  60                 }
  61         } else {
  62                 /* Token holder came in again! */
  63                 current->mm->token_priority += 2;
  64         }
  65
  66 out:
  67         current->mm->faultstamp = global_faults;
  68         current->mm->last_interval = current_interval;
  69         spin_unlock(&swap_token_lock);
  70 return;
  71 }
  72
  73 /* Called on process exit. */
  74 void __put_swap_token(struct mm_struct *mm)
  75 {
  76         spin_lock(&swap_token_lock);
  77         if (likely(mm == swap_token_mm))
  78                 swap_token_mm = NULL;
  79         spin_unlock(&swap_token_lock);
  80 }