From d4f9d02b9151b9ff87a950ed42220de4f740d27b Mon Sep 17 00:00:00 2001 From: Rik van Riel Date: Sun, 22 Aug 2004 22:59:16 -0700 Subject: [PATCH] [PATCH] token based thrashing control The following experimental patch implements token based thrashing protection, using the algorithm described in: http://www.cs.wm.edu/~sjiang/token.htm When there are pageins going on, a task can grab a token, that protects the task from pageout (except by itself) until it is no longer doing heavy pageins, or until the maximum hold time of the token is over. If the maximum hold time is exceeded, the task isn't eligable to hold the token for a while more, since it wasn't doing it much good anyway. I have run a very unscientific benchmark on my system to test the effectiveness of the patch, timing how a 230MB two-process qsbench run takes, with and without the token thrashing protection present. normal 2.6.8-rc6: 6m45s 2.6.8-rc6 + token: 4m24s This is a quick hack, implemented without having talked to the inventor of the algorithm. He's copied on the mail and I suspect we'll be able to do better than my quick implementation ... Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/sched.h | 4 ++ include/linux/swap.h | 22 +++++++++- kernel/fork.c | 2 + mm/Makefile | 2 +- mm/filemap.c | 1 + mm/memory.c | 1 + mm/rmap.c | 3 ++ mm/thrash.c | 98 +++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 131 insertions(+), 2 deletions(-) create mode 100644 mm/thrash.c diff --git a/include/linux/sched.h b/include/linux/sched.h index 65256f313eb69..a01f849da7a5a 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -220,6 +220,10 @@ struct mm_struct { /* Architecture-specific MM context */ mm_context_t context; + /* Token based thrashing protection. */ + unsigned long swap_token_time; + char recent_pagein; + /* coredumping support */ int core_waiters; struct completion *core_startup_done, core_done; diff --git a/include/linux/swap.h b/include/linux/swap.h index b081066b5f113..371e8260c577c 100644 --- a/include/linux/swap.h +++ b/include/linux/swap.h @@ -204,7 +204,6 @@ extern void free_pages_and_swap_cache(struct page **, int); extern struct page * lookup_swap_cache(swp_entry_t); extern struct page * read_swap_cache_async(swp_entry_t, struct vm_area_struct *vma, unsigned long addr); - /* linux/mm/swapfile.c */ extern long total_swap_pages; extern unsigned int nr_swapfiles; @@ -229,6 +228,22 @@ extern spinlock_t swaplock; #define swap_device_lock(p) spin_lock(&p->sdev_lock) #define swap_device_unlock(p) spin_unlock(&p->sdev_lock) +/* linux/mm/thrash.c */ +extern struct mm_struct * swap_token_mm; +extern void grab_swap_token(void); +extern void __put_swap_token(struct mm_struct *); + +static inline int has_swap_token(struct mm_struct *mm) +{ + return (mm == swap_token_mm); +} + +static inline void put_swap_token(struct mm_struct *mm) +{ + if (has_swap_token(mm)) + __put_swap_token(mm); +} + #else /* CONFIG_SWAP */ #define total_swap_pages 0 @@ -266,6 +281,11 @@ static inline swp_entry_t get_swap_page(void) return entry; } +/* linux/mm/thrash.c */ +#define put_swap_token(x) do { } while(0) +#define grab_swap_token() do { } while(0) +#define has_swap_token(x) 0 + #endif /* CONFIG_SWAP */ #endif /* __KERNEL__*/ #endif /* _LINUX_SWAP_H */ diff --git a/kernel/fork.c b/kernel/fork.c index 233dd7f190d68..601abf6bbbb80 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -29,6 +29,7 @@ #include #include #include +#include #include #include #include @@ -461,6 +462,7 @@ void mmput(struct mm_struct *mm) spin_unlock(&mmlist_lock); exit_aio(mm); exit_mmap(mm); + put_swap_token(mm); mmdrop(mm); } } diff --git a/mm/Makefile b/mm/Makefile index d22feb38a1f99..366e50de11bd5 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -12,6 +12,6 @@ obj-y := bootmem.o filemap.o mempool.o oom_kill.o fadvise.o \ readahead.o slab.o swap.o truncate.o vmscan.o \ $(mmu-y) -obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o +obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o obj-$(CONFIG_HUGETLBFS) += hugetlb.o obj-$(CONFIG_NUMA) += mempolicy.o diff --git a/mm/filemap.c b/mm/filemap.c index 0441476364105..a29efae1832c8 100644 --- a/mm/filemap.c +++ b/mm/filemap.c @@ -1195,6 +1195,7 @@ no_cached_page: * effect. */ error = page_cache_read(file, pgoff); + grab_swap_token(); /* * The page we want has now been added to the page cache. diff --git a/mm/memory.c b/mm/memory.c index 57f869fc54ca0..8dfcd810f78e2 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -1351,6 +1351,7 @@ static int do_swap_page(struct mm_struct * mm, /* Had to read the page from swap area: Major fault */ ret = VM_FAULT_MAJOR; inc_page_state(pgmajfault); + grab_swap_token(); } mark_page_accessed(page); diff --git a/mm/rmap.c b/mm/rmap.c index d4208d6d8eff4..1cb3353daa16d 100644 --- a/mm/rmap.c +++ b/mm/rmap.c @@ -230,6 +230,9 @@ static int page_referenced_one(struct page *page, if (ptep_clear_flush_young(vma, address, pte)) referenced++; + if (mm != current->mm && has_swap_token(mm)) + referenced++; + (*mapcount)--; out_unmap: diff --git a/mm/thrash.c b/mm/thrash.c new file mode 100644 index 0000000000000..7183937b24e5d --- /dev/null +++ b/mm/thrash.c @@ -0,0 +1,98 @@ +/* + * mm/thrash.c + * + * Copyright (C) 2004, Red Hat, Inc. + * Copyright (C) 2004, Rik van Riel + * Released under the GPL, see the file COPYING for details. + * + * Simple token based thrashing protection, using the algorithm + * described in: http://www.cs.wm.edu/~sjiang/token.pdf + */ +#include +#include +#include +#include + +static spinlock_t swap_token_lock = SPIN_LOCK_UNLOCKED; +static unsigned long swap_token_timeout; +unsigned long swap_token_check; +struct mm_struct * swap_token_mm = &init_mm; + +#define SWAP_TOKEN_CHECK_INTERVAL (HZ * 2) +#define SWAP_TOKEN_TIMEOUT (HZ * 300) + +/* + * 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; +} + +/* + * 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; + + /* We have the token. Let others know we still need it. */ + if (has_swap_token(current->mm)) { + current->mm->recent_pagein = 1; + return; + } + + if (time_after(jiffies, swap_token_check)) { + + /* Can't get swapout protection if we exceed our RSS limit. */ + // if (current->mm->rss > current->mm->rlimit_rss) + // return; + + /* ... or if we recently held the token. */ + if (time_before(jiffies, current->mm->swap_token_time)) + return; + + if (!spin_trylock(&swap_token_lock)) + return; + + swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL; + + mm = swap_token_mm; + if ((reason = should_release_swap_token(mm))) { + unsigned long eligible = jiffies; + if (reason == SWAP_TOKEN_TIMED_OUT) { + eligible += SWAP_TOKEN_TIMEOUT; + } + mm->swap_token_time = eligible; + swap_token_timeout = jiffies + SWAP_TOKEN_TIMEOUT; + swap_token_mm = current->mm; + } + 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)) { + swap_token_mm = &init_mm; + swap_token_check = jiffies; + } + spin_unlock(&swap_token_lock); +} -- 2.53.0