CART Implementation v3
Subsystems (10)
cover CART Implementation v3
Hi All,
Here my latest efforts on implementing CART, an advanced page replacement policy.
It seems pretty stable, except for a spurious OOM. However it yet has to run on something other than UML.
A complete CART implementation should be present in cart-cart.patch. The cart-cart-r.patch improves thereon by keeping a 3th adaptive parameter which measures the amount of fresh pages (not in |T1| u |T2| u |B1| u |B2|). When the amount of fresh pages drops below the number of longterm pages we start to reclaim pages that have just been inserted.
This works very well for a simple looped linear scan larger than the total resident set. Also it doesn't seem to regress normal workloads.
More test{s,ing} needed.
Kind regards,
Peter Zijlstra
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 1/7 CART Implementation v3
include/linux/swap.h +23 -0
@@ -154,6 +154,22 @@ extern void out_of_memory(unsigned int _/* linux/mm/memory.c */ extern void swapin_readahead (swp_entry_t ,unsigned long ,struct vm_area_struct *); +/* linux/mm/nonresident.c */ +#define NR_b1 0 +#define NR_b2 1 +#define NR_free 2 +#define NR_lost 3 + +#define NR_listid 3 +#define NR_found 0x80000000 + + +extern int nonresident_put (struct address_space *,unsigned long ,int ,int ); +extern int nonresident_find (struct address_space *,unsigned long ); +extern unsigned int nonresident_count (int ); +extern unsigned int nonresident_total (void ); +extern void nonresident_init (void ); +/* linux/mm/page_alloc.c */ extern unsigned long totalram_pages;extern unsigned long totalhigh_pages;
@@ -292,6 +308,13 @@ static inline swp_entry_t get_swap_page(#define grab_swap_token () do { } while(0)#define has_swap_token (x) 0 +/* linux/mm/nonresident.c */ +#define nonresident_put (w,x,y,z) 0 +#define nonresident_find (x,y) 0 +#define nonresident_count (x) 0 +#define nonresident_total () 0 +#define nonresident_init () do { } while (0) +#endif /* CONFIG_SWAP */ #endif /* __KERNEL__*/ #endif /* _LINUX_SWAP_H */
init/main.c +2 -0
@@ -47,6 +47,7 @@#include <linux/rmap.h> #include <linux/mempolicy.h> #include <linux/key.h> +#include <linux/swap.h> #include <asm/io.h> #include <asm/bugs.h>
@@ -494,6 +495,7 @@ asmlinkage void __init start_kernel(void }#endif vfs_caches_init_early (); +nonresident_init ();mem_init ();kmem_cache_init ();setup_per_cpu_pageset ();
mm/Makefile +2 -1
@@ -12,7 +12,8 @@ obj-y := bootmem.o filemap.o mempool.o readahead.o slab.o swap.o truncate.o vmscan.o \ prio_tree.o $(mmu-y) -obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o +obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o \ + nonresident.o obj-$(CONFIG_HUGETLBFS) += hugetlb.o obj-$(CONFIG_NUMA) += mempolicy.o obj-$(CONFIG_SPARSEMEM) += sparse.o
mm/nonresident.c new file +372 -0
372 lines not on this page · raw message
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 2/7 CART Implementation v3
In reply to [email protected]fs/proc/proc_misc.c +15 -0
@@ -233,6 +233,20 @@ static struct file_operations proc_zonei .release = seq_release, }; +extern struct seq_operations nonresident_op; +static int nonresident_open (struct inode *inode,struct file *file) +{ + (void )inode; +return seq_open (file, &nonresident_op); +} + +static struct file_operations nonresident_file_operations = { + .open = nonresident_open, + .read = seq_read, + .llseek = seq_lseek, + .release = seq_release, +}; +static int version_read_proc (char *page,char **start,off_t off,int count,int *eof,void *data) {
@@ -602,6 +616,7 @@ void __init proc_misc_init(void)create_seq_entry ("interrupts" ,0 , &proc_interrupts_operations);create_seq_entry ("slabinfo" ,S_IWUSR |S_IRUGO ,&proc_slabinfo_operations);create_seq_entry ("buddyinfo" ,S_IRUGO , &fragmentation_file_operations); +create_seq_entry ("nonresident" ,S_IRUGO , &nonresident_file_operations);create_seq_entry ("vmstat" ,S_IRUGO , &proc_vmstat_file_operations);create_seq_entry ("zoneinfo" ,S_IRUGO , &proc_zoneinfo_file_operations);create_seq_entry ("diskstats" ,0 , &proc_diskstats_operations);
mm/nonresident.c +80 -0
83 lines not on this page · raw message
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 3/7 CART Implementation v3
In reply to [email protected]include/linux/mm_inline.h +6 -31
@@ -1,40 +1,15 @@ - -static inline void -add_page_to_active_list (struct zone *zone,struct page *page) -{ -list_add (&page->lru, &zone->active_list); - zone->nr_active++; -} - -static inline void -add_page_to_inactive_list (struct zone *zone,struct page *page) -{ -list_add (&page->lru, &zone->inactive_list); - zone->nr_inactive++; -} - -static inline void -del_page_from_active_list (struct zone *zone,struct page *page) -{ -list_del (&page->lru); - zone->nr_active--; -} - -static inline void -del_page_from_inactive_list (struct zone *zone,struct page *page) -{ -list_del (&page->lru); - zone->nr_inactive--; -} -static inline void del_page_from_lru (struct zone *zone,struct page *page) {list_del (&page->lru); -if (PageActive (page)) { -ClearPageActive (page); +if (TestClearPageActive (page)) { zone->nr_active--; }else { zone->nr_inactive--; } +if (TestClearPageLongTerm (page)) { +/* zone->nr_longterm--; */ + }else { + zone->nr_shortterm--; + } }
include/linux/mmzone.h +8 -3
@@ -143,13 +143,18 @@ struct zone {ZONE_PADDING (_pad1_)/* Fields commonly accessed by the page reclaim scanner */ - spinlock_t lru_lock; -struct list_head active_list; -struct list_head inactive_list; + spinlock_t lru_lock; +struct list_head active_list;/* The T1 list of CART */ +struct list_head inactive_list;/* The T2 list of CART */ unsigned long nr_scan_active;unsigned long nr_scan_inactive;unsigned long nr_active;unsigned long nr_inactive; +unsigned long nr_evicted_active; +unsigned long nr_evicted_inactive; +unsigned long nr_shortterm;/* number of short term pages */ +unsigned long nr_p;/* p from the CART paper */ +unsigned long nr_q;/* q from the cart paper */ unsigned long pages_scanned;/* since last reclaim */ int all_unreclaimable;/* All pages pinned */
include/linux/page-flags.h +15 -0
@@ -76,6 +76,9 @@#define PG_nosave_free 18/* Free, should not be written */ #define PG_uncached 19/* Page has been mapped as uncached */ +#define PG_longterm 20/* Filter bit for CART see mm/cart.c */ +#define PG_new 21/* New page, skip first reference */ +/* * Global page accounting. One instance per CPU. Only unsigned longs are * allowed.
@@ -305,6 +308,18 @@ extern void __mod_page_state(unsigned lo#define SetPageUncached (page) set_bit(PG_uncached, &(page)->flags)#define ClearPageUncached (page) clear_bit(PG_uncached, &(page)->flags) +#define PageLongTerm (page) test_bit(PG_longterm, &(page)->flags) +#define SetPageLongTerm (page) set_bit(PG_longterm, &(page)->flags) +#define TestSetPageLongTerm (page) test_and_set_bit(PG_longterm, &(page)->flags) +#define ClearPageLongTerm (page) clear_bit(PG_longterm, &(page)->flags) +#define TestClearPageLongTerm (page) test_and_clear_bit(PG_longterm, &(page)->flags) + +#define PageNew (page) test_bit(PG_new, &(page)->flags) +#define SetPageNew (page) set_bit(PG_new, &(page)->flags) +#define TestSetPageNew (page) test_and_set_bit(PG_new, &(page)->flags) +#define ClearPageNew (page) clear_bit(PG_new, &(page)->flags) +#define TestClearPageNew (page) test_and_clear_bit(PG_new, &(page)->flags) +struct page ;/* forward declaration */ int test_clear_page_dirty (struct page *page);
include/linux/swap.h +18 -0
@@ -7,6 +7,7 @@#include <linux/mmzone.h> #include <linux/list.h> #include <linux/sched.h> +#include <linux/mm.h> #include <asm/atomic.h> #include <asm/page.h>
@@ -170,6 +171,23 @@ extern unsigned int nonresident_count(inextern unsigned int nonresident_total (void );extern void nonresident_init (void ); +/* linux/mm/cart.c */ +extern void cart_init (void ); +extern void __cart_insert (struct zone *,struct page *); +extern unsigned long cart_replace (struct zone *,struct list_head *,unsigned long ,unsigned long *); +extern void cart_reinsert (struct zone *,struct list_head *); +extern void __cart_rotate_reclaimable (struct zone *,struct page *); +extern void __cart_remember (struct zone *,struct page *); + +static inline void cart_remember (struct page *page) +{ +unsigned long flags; +struct zone *zone =page_zone (page); +spin_lock_irqsave (&zone->lru_lock, flags); +__cart_remember (zone, page); +spin_unlock_irqrestore (&zone->lru_lock, flags); +} +/* linux/mm/page_alloc.c */ extern unsigned long totalram_pages;extern unsigned long totalhigh_pages;
init/main.c +1 -0
@@ -497,6 +497,7 @@ asmlinkage void __init start_kernel(voidvfs_caches_init_early ();nonresident_init ();mem_init (); +cart_init ();kmem_cache_init ();setup_per_cpu_pageset ();numa_policy_init ();
mm/Makefile +1 -1
@@ -13,7 +13,7 @@ obj-y := bootmem.o filemap.o mempool.o prio_tree.o $(mmu-y) obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o \ - nonresident.o + nonresident.o cart.o obj-$(CONFIG_HUGETLBFS) += hugetlb.o obj-$(CONFIG_NUMA) += mempolicy.o obj-$(CONFIG_SPARSEMEM) += sparse.o
mm/cart.c new file +623 -0
623 lines not on this page · raw message
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 4/7 CART Implementation v3
In reply to [email protected]mm/cart.c +34 -2
@@ -63,6 +63,7 @@#define cart_p ((zone)->nr_p)#define cart_q ((zone)->nr_q) +#define cart_r ((zone)->nr_r)#define size_B1 ((zone)->nr_evicted_active)#define size_B2 ((zone)->nr_evicted_inactive)
@@ -81,6 +82,7 @@ void __init cart_init(void) zone->nr_shortterm =0 ; zone->nr_p =0 ; zone->nr_q =0 ; + zone->nr_r =0 ; } }
@@ -123,6 +125,12 @@ void __cart_insert(struct zone *zone, st rflags =nonresident_find (page_mapping (page),page_index (page));if (rflags & NR_found) { + ratio = (nr_Nl / (nr_Ns +1 )) ?:1 ; +if (cart_r > ratio) + cart_r -= ratio; +else + cart_r =0UL ; + rflags &= NR_listid;if (rflags == NR_b1) {if (likely (size_B1)) --size_B1;
@@ -149,6 +157,11 @@ void __cart_insert(struct zone *zone, st }/* ++nr_Nl; */ }else { + ratio = (nr_Ns / (nr_Nl +1 )) ?:1 ; + cart_r += ratio; +if (cart_r > cart_cT) + cart_r = cart_cT; +ClearPageLongTerm (page); ++nr_Ns; }
@@ -360,6 +373,7 @@ static unsigned long cart_rebalance_T2(s* returns whether there are pages on @l_t1_head */ static unsigned long cart_rebalance_T1 (struct zone *zone,struct list_head *l_t1_head, +struct list_head *l_new,unsigned long nr_dst,unsigned long *nr_scanned,struct pagevec *pvec) {
@@ -384,7 +398,11 @@ static unsigned long cart_rebalance_T1(s referenced =page_referenced (page,0 ,0 ); new =TestClearPageNew (page); -if (referenced) { +if (cart_r < nr_Nl &&PageLongTerm (page) && new) { +list_move_tail (&page->lru, l_new); +ClearPageActive (page); + ++dq; + }else if (referenced) {list_move_tail (&page->lru, &l_t1);// XXX: we race a bit here; do we mind and put it under lru_lock? /* ( |T1| >= min(p + 1, |B1|) ) and ( filter = 'S' ) */
@@ -432,6 +450,7 @@ unsigned long cart_replace(struct zone * unsigned long nr_dst, unsigned long *nr_scanned) { struct page *page; +LIST_HEAD (l_new);LIST_HEAD (l_t1);LIST_HEAD (l_t2);struct pagevec pvec;
@@ -454,12 +473,24 @@ unsigned long cart_replace(struct zone *if (list_empty (&l_t2))cart_rebalance_T2 (zone, &l_t2, nr_dst/2 , nr_scanned, &pvec);if (list_empty (&l_t1)) -cart_rebalance_T1 (zone, &l_t1, nr_dst/2 , nr_scanned, &pvec); +cart_rebalance_T1 (zone, &l_t1, &l_new, nr_dst/2 , nr_scanned, &pvec);if (list_empty (&l_t1) &&list_empty (&l_t2))break ;spin_lock_irq (&zone->lru_lock); +while (!list_empty (&l_new) && nr < nr_dst) { + page =head_to_page (&l_new); +prefetchw_next_lru_page (page, &l_new, flags); + +if (!TestClearPageLRU (page)) +BUG (); +if (!PageLongTerm (page)) +BUG (); + --size_T2; + ++nr; +list_move (&page->lru, dst); + }while (!list_empty (&l_t1) && (size_T1 > cart_p || !size_T2) && nr < nr_dst) { page =head_to_page (&l_t1);
@@ -496,6 +527,7 @@ unsigned long cart_replace(struct zone *spin_lock_irq (&zone->lru_lock);__cart_list_splice_release (zone, &l_t1, list_T1, &pvec);__cart_list_splice_release (zone, &l_t2, list_T2, &pvec); +__cart_list_splice_release (zone, &l_new, list_T2, &pvec);spin_unlock_irq (&zone->lru_lock);pagevec_release (&pvec);
include/linux/mmzone.h +1 -0
@@ -155,6 +155,7 @@ struct zone {unsigned long nr_shortterm;/* number of short term pages */ unsigned long nr_p;/* p from the CART paper */ unsigned long nr_q;/* q from the cart paper */ +unsigned long nr_r;unsigned long pages_scanned;/* since last reclaim */ int all_unreclaimable;/* All pages pinned */
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 5/7 CART Implementation v3
In reply to [email protected]fs/proc/proc_misc.c +15 -0
@@ -233,6 +233,20 @@ static struct file_operations proc_zonei .release = seq_release, }; +extern struct seq_operations cart_op; +static int cart_open (struct inode *inode,struct file *file) +{ + (void )inode; +return seq_open (file, &cart_op); +} + +static struct file_operations cart_file_operations = { + .open = cart_open, + .read = seq_read, + .llseek = seq_lseek, + .release = seq_release, +}; +extern struct seq_operations nonresident_op;static int nonresident_open (struct inode *inode,struct file *file) {
@@ -616,6 +630,7 @@ void __init proc_misc_init(void)create_seq_entry ("interrupts" ,0 , &proc_interrupts_operations);create_seq_entry ("slabinfo" ,S_IWUSR |S_IRUGO ,&proc_slabinfo_operations);create_seq_entry ("buddyinfo" ,S_IRUGO , &fragmentation_file_operations); +create_seq_entry ("cart" ,S_IRUGO , &cart_file_operations);create_seq_entry ("nonresident" ,S_IRUGO , &nonresident_file_operations);create_seq_entry ("vmstat" ,S_IRUGO , &proc_vmstat_file_operations);create_seq_entry ("zoneinfo" ,S_IRUGO , &proc_zoneinfo_file_operations);
mm/cart.c +93 -0
96 lines not on this page · raw message
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 6/7 CART Implementation v3
In reply to [email protected]mm/filemap.c +1 -9
@@ -723,7 +723,6 @@ void do_generic_mapping_read(struct addrunsigned long offset;unsigned long last_index;unsigned long next_index; -unsigned long prev_index;loff_t isize;struct page *cached_page;int error;
@@ -732,7 +731,6 @@ void do_generic_mapping_read(struct addr cached_page =NULL ; index = *ppos >>PAGE_CACHE_SHIFT ; next_index = index; - prev_index = ra.prev_page; last_index = (*ppos + desc->count +PAGE_CACHE_SIZE -1 ) >>PAGE_CACHE_SHIFT ; offset = *ppos & ~PAGE_CACHE_MASK ;
@@ -779,13 +777,7 @@ page_ok:if (mapping_writably_mapped (mapping))flush_dcache_page (page); -/* -* When (part of) the same page is read multiple times -* in succession, only mark it as accessed the first time. -*/ -if (prev_index != index) -mark_page_accessed (page); - prev_index = index; +mark_page_accessed (page);/* * Ok, we have the page, and it's up-to-date, so
mm/shmem.c +2 -5
@@ -1500,11 +1500,8 @@ static void do_shmem_file_read(struct fi*/ if (mapping_writably_mapped (mapping))flush_dcache_page (page); -/* -* Mark the page accessed if we read the beginning. -*/ -if (!offset) -mark_page_accessed (page); + +mark_page_accessed (page); }else page =ZERO_PAGE (0 );
mm/swap.c +1 -26
@@ -97,37 +97,12 @@ int rotate_reclaimable_page(struct page }/* -* FIXME: speed this up? -*/ -void fastcall activate_page(struct page *page) -{ -struct zone *zone =page_zone (page); - -spin_lock_irq (&zone->lru_lock); -if (PageLRU (page) && !PageActive (page)) { -del_page_from_inactive_list (zone, page); -SetPageActive (page); -add_page_to_active_list (zone, page); -inc_page_state (pgactivate); - } -spin_unlock_irq (&zone->lru_lock); -} - -/* * Mark a page as having seen activity. -* -* inactive,unreferenced -> inactive,referenced -* inactive,referenced -> active,unreferenced -* active,unreferenced -> active,referenced */ void fastcall mark_page_accessed(struct page *page) { -if (!PageActive (page) &&PageReferenced (page) &&PageLRU (page)) { -activate_page (page); -ClearPageReferenced (page); - }else if (!PageReferenced (page)) { +if (!PageReferenced (page))SetPageReferenced (page); - } }EXPORT_SYMBOL (mark_page_accessed);
mm/swapfile.c +2 -2
@@ -408,7 +408,7 @@ static void unuse_pte(struct vm_area_str* Move the page to the active list so it is not * immediately swapped out again after swapon. */ -activate_page (page); +SetPageReferenced (page); } static int unuse_pte_range(struct vm_area_struct *vma, pmd_t *pmd,
@@ -508,7 +508,7 @@ static int unuse_mm(struct mm_struct *mm* Activate page so shrink_cache is unlikely to unmap its * ptes while lock is dropped, so swapoff can make progress. */ -activate_page (page); +SetPageReferenced (page);unlock_page (page);down_read (&mm->mmap_sem);lock_page (page);
mm/vmscan.c +2 -23
@@ -235,27 +235,6 @@ static int shrink_slab(unsigned long scareturn ret; } -/* Called without lock on whether page is mapped, so answer is unstable */ -static inline int page_mapping_inuse (struct page *page) -{ -struct address_space *mapping; - -/* Page is in somebody's page tables. */ -if (page_mapped (page)) -return 1 ; - -/* Be more reluctant to reclaim swapcache than pagecache */ -if (PageSwapCache (page)) -return 1 ; - - mapping =page_mapping (page); -if (!mapping) -return 0 ; - -/* File is mmap'd by somebody? */ -return mapping_mapped (mapping); -} -static inline int is_page_cache_freeable (struct page *page) {return page_count (page) - !!PagePrivate (page) ==2 ;
@@ -408,8 +387,8 @@ static int shrink_list(struct list_head goto keep_locked; referenced =page_referenced (page,1 , sc->priority <=0 ); -/* In active use or really unfreeable? Activate it. */ -if (referenced &&page_mapping_inuse (page)) + +if (referenced) goto activate_locked;#ifdef CONFIG_SWAP
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
RFC PATCH 7/7 CART Implementation v3
In reply to [email protected]fs/exec.c +1 -1
@@ -331,7 +331,7 @@ void install_arg_page(struct vm_area_str goto out; }inc_mm_counter (mm, rss); -lru_cache_add_active (page); +lru_cache_add (page);set_pte_at (mm, address, pte,pte_mkdirty (pte_mkwrite (mk_pte ( page, vma->vm_page_prot))));page_add_anon_rmap (page, vma, address);
include/linux/swap.h +0 -2
@@ -199,8 +199,6 @@ extern unsigned int nr_free_pagecache_pa/* linux/mm/swap.c */ extern void FASTCALL (lru_cache_add (struct page *)); -extern void FASTCALL (lru_cache_add_active (struct page *)); -extern void FASTCALL (activate_page (struct page *));extern void FASTCALL (mark_page_accessed (struct page *));extern void lru_add_drain (void );extern int rotate_reclaimable_page (struct page *page);
mm/memory.c +3 -4
@@ -1304,7 +1304,7 @@ static int do_wp_page(struct mm_struct *page_remove_rmap (old_page);flush_cache_page (vma, address, pfn);break_cow (vma, new_page, address, page_table); -lru_cache_add_active (new_page); +lru_cache_add (new_page);page_add_anon_rmap (new_page, vma, address);/* Free the old page.. */
@@ -1782,8 +1782,7 @@ do_anonymous_page(struct mm_struct *mm, entry =maybe_mkwrite (pte_mkdirty (mk_pte (page, vma->vm_page_prot)), vma); -lru_cache_add_active (page); -SetPageReferenced (page); +lru_cache_add (page);page_add_anon_rmap (page, vma, addr); }
@@ -1903,7 +1902,7 @@ retry: entry =maybe_mkwrite (pte_mkdirty (entry), vma);set_pte_at (mm, address, page_table, entry);if (anon) { -lru_cache_add_active (new_page); +lru_cache_add (new_page);page_add_anon_rmap (new_page, vma, address); }else page_add_file_rmap (new_page);
mm/swap.c +5 -50
102 lines not on this page · raw message
mm/swap_state.c +1 -1
@@ -359,7 +359,7 @@ struct page *read_swap_cache_async(swp_e/* * Initiate read into locked page and return. */ -lru_cache_add_active (new_page); +lru_cache_add (new_page);swap_readpage (NULL , new_page);return new_page; }
mm/vmscan.c +16 -244
335 lines not on this page · raw message
--
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 8 lines · On Sun, 2005-09-11 at 22:25 +0200, [email protected] wrote:
Hi All,
Here my latest efforts on implementing CART, an advanced page replacement policy.
It seems pretty stable, except for a spurious OOM. However it yet has to run on something other than UML.
Quoted 9 lines
A complete CART implementation should be present in cart-cart.patch. The cart-cart-r.patch improves thereon by keeping a 3th adaptive parameter which measures the amount of fresh pages (not in |T1| u |T2| u |B1| u |B2|). When the amount of fresh pages drops below the number of longterm pages we start to reclaim pages that have just been inserted.
This works very well for a simple looped linear scan larger than the total resident set. Also it doesn't seem to regress normal workloads.
Some numbers. All run in an UML with mem=64M and 128M of swapspace, sync ubd.
linux-2.6.13-rc7
make -j4
real 107m15.351s user 24m4.820s sys 12m16.590s
scan 60 16
real 3m39.432s user 0m4.990s sys 0m21.920s
linux-2.6.13-rc7-cart
make -j4
real 93m18.035s user 22m44.280s sys 9m20.220s
scan 60 16
real 1m47.857s user 0m4.690s sys 0m11.690s
Signature · 1 line
Peter Zijlstra <[email protected]>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
int main(int argc, char **argv)
{
char *ptr;
int size = -1;
int loops = -1;
if (argc > 1) {
size = atoi(argv[1]);
}
if (argc > 2) {
loops = atoi(argv[2]);
}
if (size < 0) {
printf("no size specified\n");
return 0;
}
if (loops < 0) {
printf("no loops specified\n");
return 0;
}
printf("Size: %dMB\n", size);
printf("Loops: %d\n", loops);
size *= 1024*1024;
ptr = (char*)mmap(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
if (ptr) {
for (;loops; --loops) {
int i;
for (i=0; i<size; ++i) {
*(ptr + i) = loops;
}
printf(".");
fflush(stdout);
}
printf("\n");
munmap(ptr, size);
}
return 0;
}