CART Implementation

RFC PATCH In review [email protected] 3 participants 12 messages Aug 27, 2005 – Aug 29, 2005

Subsystems (10)

Memory management VFS MM core exec and binfmt +6 more subsystems

lore

Share & tools

lore

[email protected]

author

2005-08-27 22:02 UTC #0 lore raw

cover CART Implementation

Hi All,

(now split as per request)

After another day of hard work I feel I have this CART implementation complete.

It survives a pounding and the stats seem pretty stable.

The things that need more work:
1) the hash function seems pretty lousy
2) __cart_remember() called from shrink_list() needs zone->lru_lock

The whole non-resident code is based on the idea that the hash function gives an even spread so that:

B1_j B1
------ ~ ----
B2_j B2

However after a pounding the variance in (B1_j - B2_j) as given by the std. deviation: sqrt(<x^2> - <x>^2) is around 10. And this for a bucket with 57 slots.

The other issue is that __cart_remember() needs the zone->lru_lock. This function is called from shrink_list() where the lock is explicitly avoided, so this seems like an issue. Alternatives would be atomic_t for zone->nr_q or a per cpu counter delta. Suggestions?

Also I made quite some changes in swap.c and vmscan.c without being an expert on the code. Did I foul up too bad?

Then ofcourse I need to benchmark, suggestions?

Some of this code is shamelessly copied from Rik van Riel, other parts are inspired by code from Rahul Iyer.

Any comments appreciated.

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>

[email protected]

author

2005-08-27 22:02 UTC #1 lore raw

RFC PATCH 1/6 CART Implementation

include/linux/swap.h +14 -0

Index: linux-2.6-cart/include/linux/swap.h
===================================================================
@@ -154,6 +154,15 @@ 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_filter	0x01  /* short/long */
+#define NR_list		0x02  /* b1/b2; correlates to PG_active */
+#define NR_evict	0x80000000
+
+extern unsigned int remember_page(struct address_space *, unsigned long, unsigned int);
+extern unsigned int recently_evicted(struct address_space *, unsigned long);
+extern void init_nonresident(void);
+
 /* linux/mm/page_alloc.c */
 extern unsigned long totalram_pages;
 extern unsigned long totalhigh_pages;

@@ -292,6 +301,11 @@ 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 init_nonresident()	do { } while (0)
+#define remember_page(x,y,z)	0
+#define recently_evicted(x,y)	0
+
 #endif /* CONFIG_SWAP */
 #endif /* __KERNEL__*/
 #endif /* _LINUX_SWAP_H */

init/main.c +2 -0

Index: linux-2.6-cart/init/main.c
===================================================================
@@ -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();
+	init_nonresident();
 	mem_init();
 	kmem_cache_init();
 	setup_per_cpu_pageset();

mm/Makefile +2 -1

Index: linux-2.6-cart/mm/Makefile
===================================================================
@@ -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 +277 -0

277 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>

[email protected]

author

2005-08-27 22:02 UTC #2 lore raw

RFC PATCH 2/6 CART Implementation

In reply to [email protected]

fs/proc/proc_misc.c +15 -0

Index: linux-2.6-cart/fs/proc/proc_misc.c
===================================================================
@@ -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 +71 -0

74 lines not on this page · raw message

Rik van Riel

2005-08-29 03:02 UTC #3 lore raw

Quoted 4 lines · On Sat, 27 Aug 2005, [email protected] wrote:

mm/nonresident.c +4 -0

+static void bucket_stats(struct nr_bucket * nr_bucket, int * b1, int * b2)
+{
+	unsigned int i, b[2] = {0, 0};
+	for (i = 0; i < 2; ++i) {

mm/nonresident.c static int __init set_nonresident_factor · line 320

Quoted 10 lines

mm/nonresident.c +10 -0

+		unsigned int j = nr_bucket->hand[i];
+		do
+		{
+			u32 *slot = &nr_bucket->slot[j];
+			if (!!(GET_FLAGS(*slot) & NR_list) != !!i)
+				break;
+
+			j = GET_INDEX(*slot);
+			++b[i];
+		} while (j != nr_bucket->hand[i]);

Does this properly skip empty slots ?

Remember that a page that got paged in leaves a zeroed out slot in the bucket...

Signature · 6 lines

All Rights Reversed
--
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>

Peter Zijlstra

author

2005-08-29 04:15 UTC #4 lore raw

Quoted 18 lines · Rik van Riel

Quoted 4 lines · On Sat, 27 Aug 2005, [email protected] wrote:
mm/nonresident.c +4 -0
+static void bucket_stats(struct nr_bucket * nr_bucket, int * b1, int * b2)
+{
+	unsigned int i, b[2] = {0, 0};
+	for (i = 0; i < 2; ++i) {
mm/nonresident.c static int __init set_nonresident_factor · line 320
Quoted 10 lines
mm/nonresident.c +10 -0
+		unsigned int j = nr_bucket->hand[i];
+		do
+		{
+			u32 *slot = &nr_bucket->slot[j];
+			if (!!(GET_FLAGS(*slot) & NR_list) != !!i)
+				break;
+
+			j = GET_INDEX(*slot);
+			++b[i];
+		} while (j != nr_bucket->hand[i]);
Does this properly skip empty slots ?

There are no empty slots. This thing always has B1_j + B2_j = NR_SLOTS. I couldn't manage keeping track of two lists and empty slots. It doesn't really matter though. I just have to start out with |B1| = 0 and |B2| = c. I fill B2_j with zero cookies, so getting a hit there is very unlikely, that way they just get overwritten due to old age and all is well.

Quoted 4 lines

Remember that a page that got paged in leaves a zeroed out slot in the bucket...

Yeah, I was playing aroung with that. I'll change that back because it does indeed generate a problem elsewhere.

Signature · 7 lines

Peter Zijlstra <[email protected]>

--
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>

Peter Zijlstra

author

2005-08-29 06:20 UTC #5 lore raw

I'm being dense again. I really should not write these mails at 6am :-{

Quoted 20 lines · Peter Zijlstra

Quoted 18 lines · Rik van Riel
Quoted 4 lines · On Sat, 27 Aug 2005, [email protected] wrote:
mm/nonresident.c +4 -0
+static void bucket_stats(struct nr_bucket * nr_bucket, int * b1, int * b2)
+{
+	unsigned int i, b[2] = {0, 0};
+	for (i = 0; i < 2; ++i) {
mm/nonresident.c static int __init set_nonresident_factor · line 320
Quoted 10 lines
mm/nonresident.c +10 -0
+		unsigned int j = nr_bucket->hand[i];
+		do
+		{
+			u32 *slot = &nr_bucket->slot[j];
+			if (!!(GET_FLAGS(*slot) & NR_list) != !!i)
+				break;
+
+			j = GET_INDEX(*slot);
+			++b[i];
+		} while (j != nr_bucket->hand[i]);
Does this properly skip empty slots ?

I should idd skip 0 cookie slots for the stats. The hidden assumption was that the balance would not be disturbed by these null cookies; which is not obvious true. Thanks for the hint.

Quoted 7 lines

There are no empty slots. This thing always has B1_j + B2_j = NR_SLOTS. I couldn't manage keeping track of two lists and empty slots. It doesn't really matter though. I just have to start out with |B1| = 0 and |B2| = c. I fill B2_j with zero cookies, so getting a hit there is very unlikely, that way they just get overwritten due to old age and all is well.

I could ofcourse make the head 1 byte and have 4 list heads in there, that way I even have 1 spare. I'll see what kind of mess that would give ;-).

Quoted 6 lines

Quoted 4 lines
Remember that a page that got paged in leaves a zeroed out slot in the bucket...
Yeah, I was playing aroung with that. I'll change that back because it does indeed generate a problem elsewhere.

should be there again in the second series I send out earlier.

--
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>

[email protected]

author

2005-08-27 22:03 UTC #6 lore raw

RFC PATCH 3/6 CART Implementation

In reply to [email protected]

include/linux/mm_inline.h +20 -2

Index: linux-2.6-cart/include/linux/mm_inline.h
===================================================================
@@ -31,10 +31,28 @@ 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--;
+	}
+}
+
+static inline void
+add_page_to_active_tail(struct zone *zone, struct page *page)
+{
+	list_add_tail(&page->lru, &zone->active_list);
+	zone->nr_active++;
+}
+
+static inline void
+add_page_to_inactive_tail(struct zone *zone, struct page *page)
+{
+        list_add_tail(&page->lru, &zone->inactive_list);
+        zone->nr_inactive++;
 }

include/linux/mmzone.h +7 -3

Index: linux-2.6-cart/include/linux/mmzone.h
===================================================================
@@ -143,13 +143,17 @@ 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_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 +8 -0

Index: linux-2.6-cart/include/linux/page-flags.h
===================================================================
@@ -76,6 +76,8 @@
 #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 */
+
 /*
  * Global page accounting.  One instance per CPU.  Only unsigned longs are
  * allowed.

@@ -305,6 +307,12 @@ 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)
+
 struct page;	/* forward declaration */
 
 int test_clear_page_dirty(struct page *page);

include/linux/swap.h +17 -0

Index: linux-2.6-cart/include/linux/swap.h
===================================================================
@@ -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>

@@ -163,6 +164,22 @@ extern unsigned int remember_page(struct
 extern unsigned int recently_evicted(struct address_space *, unsigned long);
 extern void init_nonresident(void);
 
+/* linux/mm/cart.c */
+extern void cart_init(void);
+extern void __cart_insert(struct zone *, struct page *);
+extern struct page *__cart_replace(struct zone *);
+extern void __cart_reinsert(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

Index: linux-2.6-cart/init/main.c
===================================================================
@@ -497,6 +497,7 @@ asmlinkage void __init start_kernel(void
 	vfs_caches_init_early();
 	init_nonresident();
 	mem_init();
+	cart_init();
 	kmem_cache_init();
 	setup_per_cpu_pageset();
 	numa_policy_init();

mm/Makefile +1 -1

Index: linux-2.6-cart/mm/Makefile
===================================================================
@@ -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 +243 -0

243 lines not on this page · raw message

[email protected]

author

2005-08-27 22:03 UTC #7 lore raw

RFC PATCH 4/6 CART Implementation

In reply to [email protected]

fs/proc/proc_misc.c +15 -0

Index: linux-2.6-cart/fs/proc/proc_misc.c
===================================================================
@@ -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 +86 -0

89 lines not on this page · raw message

[email protected]

author

2005-08-27 22:03 UTC #8 lore raw

RFC PATCH 5/6 CART Implementation

In reply to [email protected]

mm/filemap.c +1 -9

Index: linux-2.6-cart/mm/filemap.c
===================================================================
@@ -723,7 +723,6 @@ void do_generic_mapping_read(struct addr
 	unsigned 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

Index: linux-2.6-cart/mm/shmem.c
===================================================================
@@ -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~~

Index: linux-2.6-cart/mm/swap.c
===================================================================
@@ -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

Index: linux-2.6-cart/mm/swapfile.c
===================================================================
@@ -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 +0 ~~-21~~

Index: linux-2.6-cart/mm/vmscan.c
===================================================================
@@ -235,27 +235,6 @@ static int shrink_slab(unsigned long sca
 	return 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;

[email protected]

author

2005-08-27 22:03 UTC #9 lore raw

RFC PATCH 6/6 CART Implementation

In reply to [email protected]

fs/exec.c +1 -1

Index: linux-2.6-cart/fs/exec.c
===================================================================
@@ -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

Index: linux-2.6-cart/include/linux/swap.h
===================================================================
@@ -191,8 +191,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 +4 -3

Index: linux-2.6-cart/mm/memory.c
===================================================================
@@ -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,7 +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);
+		lru_cache_add(page);
 		SetPageReferenced(page);
 		page_add_anon_rmap(page, vma, addr);
 	}

@@ -1903,7 +1903,8 @@ 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);
+			SetPageReferenced(new_page);
 			page_add_anon_rmap(new_page, vma, address);
 		} else
 			page_add_file_rmap(new_page);

mm/swap.c +8 ~~-49~~

105 lines not on this page · raw message

mm/swap_state.c +1 -1

Index: linux-2.6-cart/mm/swap_state.c
===================================================================
@@ -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 +19 ~~-184~~

290 lines not on this page · raw message

Marcelo Tosatti

2005-08-28 00:25 UTC #10 lore raw

In reply to [email protected]

Hi Peter,

Quoted 32 lines · On Sat, Aug 27, 2005 at 11:57:56PM +0200, [email protected] wrote:

Hi All,
(now split as per request)
After another day of hard work I feel I have this CART implementation complete.
It survives a pounding and the stats seem pretty stable.
The things that need more work:
1) the hash function seems pretty lousy
2) __cart_remember() called from shrink_list() needs zone->lru_lock
The whole non-resident code is based on the idea that the hash function gives an even spread so that:
B1_j B1
------ ~ ----
B2_j B2
However after a pounding the variance in (B1_j - B2_j) as given by the std. deviation: sqrt(<x^2> - <x>^2) is around 10. And this for a bucket with 57 slots.
The other issue is that __cart_remember() needs the zone->lru_lock. This function is called from shrink_list() where the lock is explicitly avoided, so this seems like an issue. Alternatives would be atomic_t for zone->nr_q or a per cpu counter delta. Suggestions?
Also I made quite some changes in swap.c and vmscan.c without being an expert on the code. Did I foul up too bad?

Quoted 6 lines

Then ofcourse I need to benchmark, suggestions?
Some of this code is shamelessly copied from Rik van Riel, other parts are inspired by code from Rahul Iyer.
Any comments appreciated.

+/* This function selects the candidate and returns the corresponding
+ * struct page * or returns NULL in case no page can be freed.
+ */
+struct page *__cart_replace(struct zone *zone)
+{
+ struct page *page;
+ int referenced;
+
+ while (!list_empty(list_T2)) {
+ page = list_entry(list_T2->next, struct page, lru);
+
+ if (!page_referenced(page, 0, 0))
+ break;
+
+ del_page_from_inactive_list(zone, page);
+ add_page_to_active_tail(zone, page);
+ SetPageActive(page);
+
+ cart_q_inc(zone);
+ }

If you find an unreferenced page in the T2 list you don't keep a reference to it performing a search on the T1 list below? That looks bogus.

Apart from that, both while (!list_empty(list_T2)) are problematic. If there are tons of referenced pages you simply loop, unlimited? And what about the lru lock required for dealing with page->lru ?

Look at the original algorithm: it grabs SWAP_CLUSTER_MAX pages from the inactive list, puts them into a CPU local list (on the stack), releases the lru lock, and works on the isolated pages. You want something similar.

As for testing, STP is really easy:

http://www.osdl.org/lab_activities/kernel_testing/stp

+
+ while (!list_empty(list_T1)) {
+ page = list_entry(list_T1->next, struct page, lru);
+ referenced = page_referenced(page, 0, 0);

Peter Zijlstra

author

2005-08-28 08:03 UTC #11 lore raw

Quoted 22 lines · Marcelo Tosatti

(quoted diff) +20 -0

+/* This function selects the candidate and returns the corresponding
+ * struct page * or returns NULL in case no page can be freed.
+ */
+struct page *__cart_replace(struct zone *zone)
+{
+	struct page *page;
+	int referenced;
+
+	while (!list_empty(list_T2)) {
+		page = list_entry(list_T2->next, struct page, lru);
+
+		if (!page_referenced(page, 0, 0))
+			break;
+
+		del_page_from_inactive_list(zone, page);
+		add_page_to_active_tail(zone, page);
+		SetPageActive(page);
+
+		cart_q_inc(zone);
+	}

Quoted 2 lines

If you find an unreferenced page in the T2 list you don't keep a reference to it performing a search on the T1 list below? That looks bogus.

If the loop breaks (unreferenced page) the head page of T2 is the one. All other pages are moved to the tail of T1, as per the Paper.

Quoted 2 lines

Apart from that, both while (!list_empty(list_T2)) are problematic. If there are tons of referenced pages you simply loop, unlimited?

No, max |T2| times, after that the list is simply empty. As for the other loop, that can run the initial |T1| times until it encounteres the first page put on the list by the previous loop, or untill it made a full loop. page_referenced() clears the flag right?

Quoted 2 lines

And what about
the lru lock required for dealing with page->lru ?

As the __ prefix in the name suggests it is run under zone->lru_lock. I'll some comments.

Quoted 3 lines

Look at the original algorithm: it grabs SWAP_CLUSTER_MAX pages from the inactive list, puts them into a CPU local list (on the stack), releases the lru lock, and works on the isolated pages. You want something similar.

I do, look at patch 6 where I put this thing into action. isolate_lru_pages() is modified to remove nr_to_scan = SWAP_CLUSTER_MAX pages from the lists. From there on it is similar to the current code.

Quoted 4 lines

As for testing, STP is really easy:
http://www.osdl.org/lab_activities/kernel_testing/stp

Thanks, I'll have a look.

Kind regards,

Signature · 7 lines

Peter Zijlstra <[email protected]>

--
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>