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 grab_swap_token(void)29void 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 if (likely(current->mm->token_priority > 0)) 52 current->mm->token_priority--; 53 } 54 /* Check if we deserve the token */ 55 if (current->mm->token_priority > 56 swap_token_mm->token_priority) { 57 current->mm->token_priority += 2; 58 swap_token_mm = current->mm; 59 } 60 } else { 61 /* Token holder came in again! */ 62 current->mm->token_priority += 2; 63 } 64 65 out: 66 current->mm->faultstamp = global_faults; 67 current->mm->last_interval = current_interval; 68 spin_unlock(&swap_token_lock); 69 return; 70 } 71 72 /* Called on process exit. */ __put_swap_token(struct mm_struct * mm)73void __put_swap_token(struct mm_struct *mm) 74 { 75 spin_lock(&swap_token_lock); 76 if (likely(mm == swap_token_mm)) 77 swap_token_mm = NULL; 78 spin_unlock(&swap_token_lock); 79 } 80