| 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(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 | |
| 64 | out: |
| 65 | mm->faultstamp = global_faults; |
| 66 | mm->last_interval = current_interval; |
| 67 | spin_unlock(&swap_token_lock); |
| 68 | } |
| 69 | |
| 70 | /* Called on process exit. */ |
| 71 | void __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 | } |