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 25static DEFINE_SPINLOCK(swap_token_lock); 26struct mm_struct *swap_token_mm; 27static unsigned int global_faults; 28 29void grab_swap_token(struct mm_struct *mm) 30{ 31 int current_interval; 32 33 global_faults++; 34 35 current_interval = global_faults - 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 mm->token_priority = mm->token_priority + 2; 43 swap_token_mm = mm; 44 goto out; 45 } 46 47 if (mm != swap_token_mm) { 48 if (current_interval < mm->last_interval) 49 mm->token_priority++; 50 else { 51 if (likely(mm->token_priority > 0)) 52 mm->token_priority--; 53 } 54 /* Check if we deserve the token */ 55 if (mm->token_priority > swap_token_mm->token_priority) { 56 mm->token_priority += 2; 57 swap_token_mm = mm; 58 } 59 } else { 60 /* Token holder came in again! */ 61 mm->token_priority += 2; 62 } 63 64out: 65 mm->faultstamp = global_faults; 66 mm->last_interval = current_interval; 67 spin_unlock(&swap_token_lock); 68} 69 70/* Called on process exit. */ 71void __put_swap_token(struct mm_struct *mm) 72{ 73 spin_lock(&swap_token_lock); 74 if (likely(mm == swap_token_mm)) 75 swap_token_mm = NULL; 76 spin_unlock(&swap_token_lock); 77} 78