From: Peter Zijlstra <a.p.zijlstra@chello.nl>
To: linux-mm@kvack.org
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Subject: [PATCH 35/39] mm: random: random page replacement policy
Date: Wed, 12 Jul 2006 16:43:52 +0200 [thread overview]
Message-ID: <20060712144352.16998.85059.sendpatchset@lappy> (raw)
In-Reply-To: <20060712143659.16998.6444.sendpatchset@lappy>
From: Marcelo Tosatti <marcelo.tosatti@cyclades.com>
Random page replacement.
Signed-off-by: Marcelo Tosatti <marcelo.tosatti@cyclades.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
include/linux/mm_page_replace.h | 2
include/linux/mm_page_replace_data.h | 2
include/linux/mm_random_data.h | 9 +
include/linux/mm_random_policy.h | 60 +++++++++
mm/Kconfig | 5
mm/Makefile | 1
mm/random_policy.c | 218 +++++++++++++++++++++++++++++++++++
7 files changed, 297 insertions(+)
Index: linux-2.6/mm/random_policy.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6/mm/random_policy.c 2006-07-12 16:09:19.000000000 +0200
@@ -0,0 +1,218 @@
+
+/* Random page replacement policy */
+
+#include <linux/module.h>
+#include <linux/mm_page_replace.h>
+#include <linux/swap.h>
+#include <linux/pagevec.h>
+#include <linux/init.h>
+#include <linux/rmap.h>
+#include <linux/hash.h>
+#include <linux/seq_file.h>
+#include <linux/writeback.h>
+#include <linux/buffer_head.h> /* for try_to_release_page(),
+ buffer_heads_over_limit */
+#include <asm/sections.h>
+
+void __init pgrep_init(void)
+{
+ printk(KERN_ERR "Random page replacement policy init!\n");
+}
+
+void __init pgrep_init_zone(struct zone *zone)
+{
+ zone->policy.nr_pages = 0;
+}
+
+static DEFINE_PER_CPU(struct pagevec, add_pvecs) = { 0, };
+
+void fastcall pgrep_add(struct page *page)
+{
+ struct pagevec *pvec = &get_cpu_var(add_pvecs);
+
+ page_cache_get(page);
+ if (!pagevec_add(pvec, page))
+ __pagevec_pgrep_add(pvec);
+ put_cpu_var(add_pvecs);
+}
+
+void __pgrep_add_drain(unsigned int cpu)
+{
+ struct pagevec *pvec = &per_cpu(add_pvecs, cpu);
+
+ if (pagevec_count(pvec))
+ __pagevec_pgrep_add(pvec);
+}
+
+static inline void __page_release(struct zone *zone, struct page *page,
+ struct pagevec *pvec)
+{
+ BUG_ON(PageLRU(page));
+ SetPageLRU(page);
+ ++zone->policy.nr_pages;
+
+ if (!pagevec_add(pvec, page)) {
+ spin_unlock_irq(&zone->lru_lock);
+ if (buffer_heads_over_limit)
+ pagevec_strip(pvec);
+ __pagevec_release(pvec);
+ spin_lock_irq(&zone->lru_lock);
+ }
+}
+
+void pgrep_reinsert(struct list_head *page_list)
+{
+ struct page *page, *page2;
+ struct zone *zone = NULL;
+ struct pagevec pvec;
+
+ pagevec_init(&pvec, 1);
+ list_for_each_entry_safe(page, page2, page_list, lru) {
+ struct zone *pagezone = page_zone(page);
+ if (pagezone != zone) {
+ if (zone)
+ spin_unlock_irq(&zone->lru_lock);
+ zone = pagezone;
+ spin_lock_irq(&zone->lru_lock);
+ }
+ __page_release(zone, page, &pvec);
+ }
+ if (zone)
+ spin_unlock_irq(&zone->lru_lock);
+ pagevec_release(&pvec);
+}
+
+/*
+ * Lehmer simple linear congruential PRNG
+ *
+ * Xn+1 = (a * Xn + c) mod m
+ *
+ * where a, c and m are constants.
+ *
+ * Note that "m" is zone->present_pages, so in this case its
+ * really not constant.
+ */
+
+static unsigned long get_random(struct zone *zone)
+{
+ zone->policy.seed =
+ hash_long(zone->policy.seed, BITS_PER_LONG) + 3147484177UL;
+ return zone->policy.seed;
+}
+
+static struct page *pick_random_cache_page(struct zone *zone)
+{
+ struct page *page;
+ unsigned long pfn;
+ do {
+ pfn = zone->zone_start_pfn +
+ get_random(zone) % zone->present_pages;
+ page = pfn_to_page(pfn);
+ } while (!PageLRU(page));
+ zone->policy.seed ^= page_index(page);
+ return page;
+}
+
+static unsigned long pick_candidates(struct zone *zone,
+ unsigned long nr_to_scan, struct list_head *pages)
+{
+ unsigned long nr_taken = 0;
+ for (;nr_to_scan && zone->policy.nr_pages; nr_to_scan--) {
+ struct page *page = pick_random_cache_page(zone);
+ if (!TestSetPageCandidate(page)) {
+ list_add(&page->lru, pages);
+ ++nr_taken;
+ }
+ }
+ return nr_taken;
+}
+
+void __pgrep_get_candidates(struct zone *zone, int priority,
+ unsigned long nr_to_scan, struct list_head *pages,
+ unsigned long *nr_scanned)
+{
+ LIST_HEAD(candidates);
+ nr_to_scan = pick_candidates(zone, nr_to_scan, &candidates);
+ isolate_lru_pages(zone, nr_to_scan, &candidates, pages, nr_scanned);
+ while (!list_empty(&candidates)) {
+ struct page *page = lru_to_page(&candidates);
+ list_del(&page->lru);
+ ClearPageCandidate(page);
+ }
+}
+
+void pgrep_put_candidates(struct zone *zone, struct list_head *pages,
+ unsigned long nr_freed, int may_swap)
+{
+ struct pagevec pvec;
+ pagevec_init(&pvec, 1);
+ spin_lock_irq(&zone->lru_lock);
+ while (!list_empty(pages)) {
+ struct page *page = lru_to_page(pages);
+ list_del(&page->lru);
+ __page_release(zone, page, &pvec);
+ }
+ spin_unlock_irq(&zone->lru_lock);
+ pagevec_release(&pvec);
+}
+
+#define K(x) ((x) << (PAGE_SHIFT-10))
+
+void pgrep_show(struct zone *zone)
+{
+ printk("%s"
+ " free:%lukB"
+ " min:%lukB"
+ " low:%lukB"
+ " high:%lukB"
+ " cached:%lukB"
+ " present:%lukB"
+ " pages_scanned:%lu"
+ " all_unreclaimable? %s"
+ "\n",
+ zone->name,
+ K(zone->free_pages),
+ K(zone->pages_min),
+ K(zone->pages_low),
+ K(zone->pages_high),
+ K(zone->policy.nr_pages),
+ K(zone->present_pages),
+ zone->pages_scanned,
+ (zone->all_unreclaimable ? "yes" : "no")
+ );
+}
+
+void pgrep_zoneinfo(struct zone *zone, struct seq_file *m)
+{
+ seq_printf(m,
+ "\n pages free %lu"
+ "\n min %lu"
+ "\n low %lu"
+ "\n high %lu"
+ "\n cached %lu"
+ "\n scanned %lu"
+ "\n spanned %lu"
+ "\n present %lu",
+ zone->free_pages,
+ zone->pages_min,
+ zone->pages_low,
+ zone->pages_high,
+ zone->policy.nr_pages,
+ zone->pages_scanned,
+ zone->spanned_pages,
+ zone->present_pages);
+}
+
+void __pgrep_counts(unsigned long *active, unsigned long *inactive,
+ unsigned long *free, struct zone *zones)
+{
+ int i;
+
+ *active = 0;
+ *inactive = 0;
+ *free = 0;
+ for (i = 0; i < MAX_NR_ZONES; i++) {
+ *free += zones[i].free_pages;
+ }
+}
+
Index: linux-2.6/mm/Kconfig
===================================================================
--- linux-2.6.orig/mm/Kconfig 2006-07-12 16:09:19.000000000 +0200
+++ linux-2.6/mm/Kconfig 2006-07-12 16:11:22.000000000 +0200
@@ -158,6 +158,11 @@ config MM_POLICY_CART_R
This option selects a CART based policy modified to handle cyclic
access patterns.
+config MM_POLICY_RANDOM
+ bool "Random"
+ help
+ This option selects the random replacement policy.
+
endchoice
#
Index: linux-2.6/include/linux/mm_page_replace.h
===================================================================
--- linux-2.6.orig/include/linux/mm_page_replace.h 2006-07-12 16:09:19.000000000 +0200
+++ linux-2.6/include/linux/mm_page_replace.h 2006-07-12 16:09:19.000000000 +0200
@@ -102,6 +102,8 @@ extern void __pgrep_counts(unsigned long
#include <linux/mm_clockpro_policy.h>
#elif defined CONFIG_MM_POLICY_CART || defined CONFIG_MM_POLICY_CART_R
#include <linux/mm_cart_policy.h>
+#elif defined CONFIG_MM_POLICY_RANDOM
+#include <linux/mm_random_policy.h>
#else
#error no mm policy
#endif
Index: linux-2.6/include/linux/mm_page_replace_data.h
===================================================================
--- linux-2.6.orig/include/linux/mm_page_replace_data.h 2006-07-12 16:09:19.000000000 +0200
+++ linux-2.6/include/linux/mm_page_replace_data.h 2006-07-12 16:09:19.000000000 +0200
@@ -9,6 +9,8 @@
#include <linux/mm_clockpro_data.h>
#elif defined CONFIG_MM_POLICY_CART || defined CONFIG_MM_POLICY_CART_R
#include <linux/mm_cart_data.h>
+#elif defined CONFIG_MM_POLICY_RANDOM
+#include <linux/mm_random_data.h>
#else
#error no mm policy
#endif
Index: linux-2.6/include/linux/mm_random_policy.h
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6/include/linux/mm_random_policy.h 2006-07-12 16:09:19.000000000 +0200
@@ -0,0 +1,60 @@
+#ifndef _LINUX_MM_RANDOM_POLICY_H
+#define _LINUX_MM_RANDOM_POLICY_H
+
+#ifdef __KERNEL__
+
+#include <linux/page-flags.h>
+
+#define PG_candidate PG_reclaim1
+
+#define PageCandidate(page) test_bit(PG_candidate, &(page)->flags)
+#define TestSetPageCandidate(page) test_and_set_bit(PG_candidate, &(page)->flags)
+#define ClearPageCandidate(page) clear_bit(PG_candidate, &(page)->flags)
+
+#define pgrep_hint_active(p) do { } while (0)
+#define pgrep_hint_use_once(p) do { } while (0)
+
+static inline
+void __pgrep_add(struct zone *zone, struct page *page)
+{
+ zone->policy.nr_pages++;
+}
+
+#define pgrep_activate(p) 0
+#define pgrep_reclaimable(p) RECLAIM_OK
+#define pgrep_mark_accessed(p) do { } while (0)
+
+static inline
+void __pgrep_remove(struct zone *zone, struct page *page)
+{
+ if (PageCandidate(page)) {
+ ClearPageCandidate(page);
+ list_del(&page->lru);
+ }
+ zone->policy.nr_pages--;
+}
+
+static inline
+void __pgrep_rotate_reclaimable(struct zone *zone, struct page *page)
+{
+}
+
+#define pgrep_copy_state(d, s) do { } while (0)
+#define pgrep_clear_state(p) do { } while (0)
+#define pgrep_is_active(p) 0
+
+#define pgrep_remember(z, p) do { } while (0)
+#define pgrep_forget(m, i) do { } while (0)
+
+static inline unsigned long __pgrep_nr_pages(struct zone *zone)
+{
+ return zone->policy.nr_pages;
+}
+
+static inline unsigned long __pgrep_nr_scan(struct zone *zone)
+{
+ return zone->policy.nr_pages;
+}
+
+#endif /* __KERNEL__ */
+#endif /* _LINUX_MM_LRU_POLICY_H */
Index: linux-2.6/include/linux/mm_random_data.h
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6/include/linux/mm_random_data.h 2006-07-12 16:09:19.000000000 +0200
@@ -0,0 +1,9 @@
+#ifdef __KERNEL__
+
+struct pgrep_data {
+ unsigned long nr_scan;
+ unsigned long nr_pages;
+ unsigned long seed;
+};
+
+#endif /* __KERNEL__ */
Index: linux-2.6/mm/Makefile
===================================================================
--- linux-2.6.orig/mm/Makefile 2006-07-12 16:09:19.000000000 +0200
+++ linux-2.6/mm/Makefile 2006-07-12 16:11:22.000000000 +0200
@@ -16,6 +16,7 @@ obj-$(CONFIG_MM_POLICY_USEONCE) += useon
obj-$(CONFIG_MM_POLICY_CLOCKPRO) += nonresident.o clockpro.o
obj-$(CONFIG_MM_POLICY_CART) += nonresident-cart.o cart.o
obj-$(CONFIG_MM_POLICY_CART_R) += nonresident-cart.o cart.o
+obj-$(CONFIG_MM_POLICY_RANDOM) += random_policy.o
obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o
obj-$(CONFIG_HUGETLBFS) += hugetlb.o
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2006-07-12 14:43 UTC|newest]
Thread overview: 44+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-07-12 14:36 [PATCH 0/39] mm: 2.6.17-pr1 - generic page-replacement framework and 4 new policies Peter Zijlstra
2006-07-12 14:37 ` [PATCH 1/39] mm: disuse activate_page() Peter Zijlstra
2006-07-12 14:37 ` [PATCH 2/39] mm: adjust blk_congestion_wait() logic Peter Zijlstra
2006-07-12 14:37 ` [PATCH 3/39] mm: pgrep: prepare for page replace framework Peter Zijlstra
2006-07-12 14:37 ` [PATCH 4/39] mm: pgrep: convert insertion Peter Zijlstra
2006-07-12 14:37 ` [PATCH 5/39] mm: pgrep: add a use-once insertion hint Peter Zijlstra
2006-07-12 14:38 ` [PATCH 6/39] mm: pgrep: generice __pagevec_*_add Peter Zijlstra
2006-07-12 14:38 ` [PATCH 7/39] mm: pgrep: abstract the activation logic Peter Zijlstra
2006-07-12 14:38 ` [PATCH 8/39] mm: pgrep: move useful macros around Peter Zijlstra
2006-07-12 14:38 ` [PATCH 9/39] mm: pgrep: move struct scan_control around Peter Zijlstra
2006-07-12 14:38 ` [PATCH 10/39] mm: pgrep: isolate the reclaim_mapped logic Peter Zijlstra
2006-07-12 14:39 ` [PATCH 11/39] mm: pgrep: replace mark_page_accessed Peter Zijlstra
2006-07-12 14:39 ` [PATCH 12/39] mm: pgrep: move the shrink logic Peter Zijlstra
2006-07-12 14:39 ` [PATCH 13/39] mm: pgrep: abstract rotate_reclaimable_page() Peter Zijlstra
2006-07-12 14:39 ` [PATCH 14/39] mm: pgrep: manage page-state Peter Zijlstra
2006-07-12 14:39 ` [PATCH 15/39] mm: pgrep: abstract page removal Peter Zijlstra
2006-07-12 14:40 ` [PATCH 16/39] mm: pgrep: remove mm_inline.h Peter Zijlstra
2006-07-12 14:40 ` [PATCH 17/39] mm: pgrep: re-insertion logic Peter Zijlstra
2006-07-12 14:40 ` [PATCH 18/39] mm: pgrep: initialisation hooks Peter Zijlstra
2006-07-12 14:40 ` [PATCH 19/39] mm: pgrep: info functions Peter Zijlstra
2006-07-12 14:40 ` [PATCH 20/39] mm: pgrep: page count functions Peter Zijlstra
2006-07-12 14:41 ` [PATCH 21/39] mm: pgrep: per policy data Peter Zijlstra
2006-07-12 14:41 ` [PATCH 22/39] mm: pgrep: per policy PG_flags Peter Zijlstra
2006-07-12 14:41 ` [PATCH 23/39] mm: pgrep: nonresident page tracking hooks Peter Zijlstra
2006-07-12 14:41 ` [PATCH 24/39] mm: pgrep: generic shrinker logic Peter Zijlstra
2006-07-12 14:41 ` [PATCH 25/39] mm: pgrep: documentation Peter Zijlstra
2006-07-12 14:42 ` [PATCH 26/39] sum_cpu_var Peter Zijlstra
2006-07-12 14:42 ` [PATCH 27/39] mm: clockpro: nonresident page tracking for CLOCK-Pro Peter Zijlstra
2006-07-12 14:42 ` [PATCH 28/39] mm: clockpro: re-introduce page_referenced() ignore_token Peter Zijlstra
2006-07-12 14:42 ` [PATCH 29/39] mm: clockpro: second per policy PG_flag Peter Zijlstra
2006-07-12 14:42 ` [PATCH 30/39] mm: clockpro: CLOCK-Pro policy implementation Peter Zijlstra
2006-07-12 14:43 ` [PATCH 31/39] mm: cart: nonresident page tracking for CART Peter Zijlstra
2006-07-12 14:43 ` [PATCH 32/39] mm: cart: third per policy PG_flag Peter Zijlstra
2006-07-12 14:43 ` [PATCH 33/39] mm: cart: CART policy implementation Peter Zijlstra
2006-07-12 14:43 ` [PATCH 34/39] mm: cart: CART-r " Peter Zijlstra
2006-07-12 14:43 ` Peter Zijlstra [this message]
2006-07-12 14:44 ` [PATCH 36/39] mm: refault histogram for non-resident policies Peter Zijlstra
2006-07-12 14:44 ` [PATCH 37/39] mm: use-once: cleanup of the use-once logic Peter Zijlstra
2006-07-12 14:44 ` [PATCH 38/39] mm: use-once: use the generic shrinker logic Peter Zijlstra
2006-07-12 14:44 ` [PATCH 39/39] mm: use-once: cleanup of the insertion logic Peter Zijlstra
2006-07-13 15:38 ` [PATCH 0/39] mm: 2.6.17-pr1 - generic page-replacement framework and 4 new policies Christoph Lameter
2006-07-15 17:03 ` Peter Zijlstra
2006-07-16 3:50 ` Christoph Lameter
2006-07-26 10:03 ` Marcelo Tosatti
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20060712144352.16998.85059.sendpatchset@lappy \
--to=a.p.zijlstra@chello.nl \
--cc=linux-mm@kvack.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox