minimal rmap

This is the "minimal rmap" patch, writen by Rik, ported to 2.5 by Craig Kulsea.

Basically,

before: When the page reclaim code decides that is has scanned too many unreclaimable pages on the LRU it does a scan of process virtual address spaces for pages to add to swapcache. ptes pointing at the page are unmapped as the scan proceeds. When all ptes referring to a page have been unmapped and it has been written to swap the page is reclaimable.

after: When an anonymous page is encountered on the tail of the LRU we use the rmap to see if it hasn't been referenced lately. If so then add it to swapcache. When the page is again encountered on the LRU, if it is still unreferenced then try to unmap all ptes which refer to it in one hit, and if it is clean (ie: on swap) then free it.

The rest of the VM - list management, the classzone concept, etc remains unchanged.

There are a number of things which the per-page pte chain could be used for. Bill Irwin has identified the following.

(1) page replacement no longer goes around randomly unmapping things

(2) referenced bits are more accurate because there aren't several ms or even seconds between find the multiple pte's mapping a page

(3) reduces page replacement from O(total virtually mapped) to O(physical)

(4) enables defragmentation of physical memory

(5) enables cooperative offlining of memory for friendly guest instance behavior in UML and/or LPAR settings

(6) demonstrable benefit in performance of swapping which is common in end-user interactive workstation workloads (I don't like the word "desktop"). c.f. Craig Kulesa's post wrt. swapping performance

(7) evidence from 2.4-based rmap trees indicates approximate parity with mainline in kernel compiles with appropriate locking bits

(8) partitioning of physical memory can reduce the complexity of page replacement searches by scanning only the "interesting" zones implemented and merged in 2.4-based rmap

(9) partitioning of physical memory can increase the parallelism of page replacement searches by independently processing different zones implemented, but not merged in 2.4-based rmap

(10) the reverse mappings may be used for efficiently keeping pte cache attributes coherent

(11) they may be used for virtual cache invalidation (with changes)

(12) the reverse mappings enable proper RSS limit enforcement implemented and merged in 2.4-based rmap

The code adds a pointer to struct page, consumes additional storage for the pte chains and adds computational expense to the page reclaim code (I measured it at 3% additional load during streaming I/O). The benefits which we get back for all this are, I must say, theoretical and unproven. If it has real advantages (or, indeed, disadvantages) then why has nobody demonstrated them?

There are a number of things remaining to be done:

1: Demonstrate the above advantages.

2: Make it work with pte-highmem (Bill Irwin is signed up for this)

3: Don't add pte_chains to non-shared pages optimisation (Dave McCracken's
patch does this)

4: Move the pte_chains into highmem too (Bill, I guess)

5: per-cpu pte_chain freelists (Rik?)

6: maybe GC the pte_chain backing pages. (Seems unavoidable. Rik?)

7: multithread the page reclaim code. (I have patches).

8: clustered add-to-swap. Not sure if I buy this. anon pages are
often well-ordered-by-virtual-address on the LRU, so it "just works" for benchmarky loads. But there may be some other loads...

9: Fix bad IO latency in page reclaim (I have lame patches)

10: Develop tuning tools, use them.

11: The nightly updatedb run is still evicting everything.

 fs/exec.c                        |    2 
 include/asm-alpha/rmap.h         |    7 
 include/asm-arm/proc-armv/rmap.h |   49 ++++
 include/asm-arm/rmap.h           |    6 
 include/asm-cris/rmap.h          |    7 
 include/asm-generic/rmap.h       |   52 ++++
 include/asm-i386/rmap.h          |    7 
 include/asm-ia64/rmap.h          |    7 
 include/asm-m68k/rmap.h          |    7 
 include/asm-mips/rmap.h          |    7 
 include/asm-mips64/rmap.h        |    7 
 include/asm-parisc/rmap.h        |    7 
 include/asm-ppc/rmap.h           |    9 
 include/asm-s390/rmap.h          |    7 
 include/asm-s390x/rmap.h         |    7 
 include/asm-sh/rmap.h            |    7 
 include/asm-sparc/rmap.h         |    7 
 include/asm-sparc64/rmap.h       |    7 
 include/linux/mm.h               |    5 
 include/linux/page-flags.h       |   28 ++
 include/linux/swap.h             |   14 +
 kernel/fork.c                    |    4 
 mm/Makefile                      |    2 
 mm/filemap.c                     |    9 
 mm/memory.c                      |   27 +-
 mm/mremap.c                      |    8 
 mm/page_alloc.c                  |    1 
 mm/rmap.c                        |  394 ++++++++++++++++++++++++++++++++++
 mm/swap_state.c                  |   63 +++++
 mm/swapfile.c                    |    1 
 mm/vmscan.c                      |  447 +++++++--------------------------------
 31 files changed, 832 insertions(+), 380 deletions(-)

@@ -36,6 +36,7 @@
 #include <linux/spinlock.h>
 #include <linux/personality.h>
 #include <linux/binfmts.h>
+#include <linux/swap.h>
 #define __NO_VERSION__
 #include <linux/module.h>
 #include <linux/namei.h>

@@ -283,6 +284,7 @@ void put_dirty_page(struct task_struct *
 	flush_dcache_page(page);
 	flush_page_to_ram(page);
 	set_pte(pte, pte_mkdirty(pte_mkwrite(mk_pte(page, PAGE_COPY))));
+	page_add_rmap(page, pte);
 	pte_unmap(pte);
 	tsk->mm->rss++;
 	spin_unlock(&tsk->mm->page_table_lock);

@@ -0,0 +1,7 @@
+#ifndef _ALPHA_RMAP_H
+#define _ALPHA_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,6 @@
+#ifndef _ARM_RMAP_H
+#define _ARM_RMAP_H
+
+#include <asm/proc/rmap.h>
+
+#endif /* _ARM_RMAP_H */

@@ -0,0 +1,7 @@
+#ifndef _CRIS_RMAP_H
+#define _CRIS_RMAP_H
+
+/* nothing to see, move along :) */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _I386_RMAP_H
+#define _I386_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _IA64_RMAP_H
+#define _IA64_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _M68K_RMAP_H
+#define _M68K_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _MIPS64_RMAP_H
+#define _MIPS64_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _MIPS_RMAP_H
+#define _MIPS_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _PARISC_RMAP_H
+#define _PARISC_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,9 @@
+#ifndef _PPC_RMAP_H
+#define _PPC_RMAP_H
+
+/* PPC calls pte_alloc() before mem_map[] is setup ... */
+#define BROKEN_PPC_PTE_ALLOC_ONE
+
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _S390_RMAP_H
+#define _S390_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _S390X_RMAP_H
+#define _S390X_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _SH_RMAP_H
+#define _SH_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _SPARC64_RMAP_H
+#define _SPARC64_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -0,0 +1,7 @@
+#ifndef _SPARC_RMAP_H
+#define _SPARC_RMAP_H
+
+/* nothing to see, move along */
+#include <asm-generic/rmap.h>
+
+#endif

@@ -130,6 +130,9 @@ struct vm_operations_struct {
 	struct page * (*nopage)(struct vm_area_struct * area, unsigned long address, int unused);
 };
 
+/* forward declaration; pte_chain is meant to be internal to rmap.c */
+struct pte_chain;
+
 /*
  * Each physical page in the system has a struct page associated with
  * it to keep track of whatever it is we are using the page for at the

@@ -154,6 +157,8 @@ struct page {
 					   updated asynchronously */
 	struct list_head lru;		/* Pageout list, eg. active_list;
 					   protected by pagemap_lru_lock !! */
+	struct pte_chain * pte_chain;	/* Reverse pte mapping pointer.
+					 * protected by PG_chainlock */
 	unsigned long private;		/* mapping-private opaque data */
 
 	/*

@@ -47,7 +47,7 @@
  * locked- and dirty-page accounting.  The top eight bits of page->flags are
  * used for page->zone, so putting flag bits there doesn't work.
  */
-#define PG_locked	 0	/* Page is locked. Don't touch. */
+#define PG_locked	 	 0	/* Page is locked. Don't touch. */
 #define PG_error		 1
 #define PG_referenced		 2
 #define PG_uptodate		 3

@@ -65,6 +65,7 @@
 #define PG_private		12	/* Has something at ->private */
 #define PG_writeback		13	/* Page is under writeback */
 #define PG_nosave		15	/* Used for system suspend/resume */
+#define PG_chainlock		16	/* lock bit for ->pte_chain */
 
 /*
  * Global page accounting.  One instance per CPU.

@@ -217,6 +218,31 @@ extern void get_page_state(struct page_s
 #define TestClearPageNosave(page)	test_and_clear_bit(PG_nosave, &(page)->flags)
 
 /*
+ * inlines for acquisition and release of PG_chainlock
+ */
+static inline void pte_chain_lock(struct page *page)
+{
+	/*
+	 * Assuming the lock is uncontended, this never enters
+	 * the body of the outer loop. If it is contended, then
+	 * within the inner loop a non-atomic test is used to
+	 * busywait with less bus contention for a good time to
+	 * attempt to acquire the lock bit.
+	 */
+	preempt_disable();
+	while (test_and_set_bit(PG_chainlock, &page->flags)) {
+		while (test_bit(PG_chainlock, &page->flags))
+			cpu_relax();
+	}
+}
+
+static inline void pte_chain_unlock(struct page *page)
+{
+	clear_bit(PG_chainlock, &page->flags);
+	preempt_enable();
+}
+
+/*
  * The PageSwapCache predicate doesn't use a PG_flag at this time,
  * but it may again do so one day.
  */

@@ -142,6 +142,19 @@ struct sysinfo;
 struct address_space;
 struct zone_t;
 
+/* linux/mm/rmap.c */
+extern int FASTCALL(page_referenced(struct page *));
+extern void FASTCALL(page_add_rmap(struct page *, pte_t *));
+extern void FASTCALL(page_remove_rmap(struct page *, pte_t *));
+extern int FASTCALL(try_to_unmap(struct page *));
+extern int FASTCALL(page_over_rsslimit(struct page *));
+
+/* return values of try_to_unmap */
+#define	SWAP_SUCCESS	0
+#define	SWAP_AGAIN	1
+#define	SWAP_FAIL	2
+#define	SWAP_ERROR	3
+
 /* linux/mm/swap.c */
 extern void FASTCALL(lru_cache_add(struct page *));
 extern void FASTCALL(__lru_cache_del(struct page *));

@@ -168,6 +181,7 @@ int rw_swap_page_sync(int rw, swp_entry_
 extern void show_swap_cache_info(void);
 #endif
 extern int add_to_swap_cache(struct page *, swp_entry_t);
+extern int add_to_swap(struct page *);
 extern void __delete_from_swap_cache(struct page *page);
 extern void delete_from_swap_cache(struct page *page);
 extern int move_to_swap_cache(struct page *page, swp_entry_t entry);

@@ -189,7 +189,6 @@ static inline int dup_mmap(struct mm_str
 	mm->map_count = 0;
 	mm->rss = 0;
 	mm->cpu_vm_mask = 0;
-	mm->swap_address = 0;
 	pprev = &mm->mmap;
 
 	/*

@@ -308,9 +307,6 @@ inline void __mmdrop(struct mm_struct *m
 void mmput(struct mm_struct *mm)
 {
 	if (atomic_dec_and_lock(&mm->mm_users, &mmlist_lock)) {
-		extern struct mm_struct *swap_mm;
-		if (swap_mm == mm)
-			swap_mm = list_entry(mm->mmlist.next, struct mm_struct, mmlist);
 		list_del(&mm->mmlist);
 		mmlist_nr--;
 		spin_unlock(&mmlist_lock);

@@ -176,14 +176,13 @@ static inline void truncate_partial_page
  */
 static void truncate_complete_page(struct page *page)
 {
-	/* Leave it on the LRU if it gets converted into anonymous buffers */
-	if (!PagePrivate(page) || do_invalidatepage(page, 0)) {
-		lru_cache_del(page);
-	} else {
+	/* Drop fs-specific data so the page might become freeable. */
+	if (PagePrivate(page) && !do_invalidatepage(page, 0)) {
 		if (current->flags & PF_INVALIDATE)
 			printk("%s: buffer heads were leaked\n",
 				current->comm);
 	}
+
 	ClearPageDirty(page);
 	ClearPageUptodate(page);
 	remove_inode_page(page);

@@ -660,7 +659,7 @@ EXPORT_SYMBOL(wait_on_page_bit);
  * But that's OK - sleepers in wait_on_page_writeback() just go back to sleep.
  *
  * The first mb is necessary to safely close the critical section opened by the
- * TryLockPage(), the second mb is necessary to enforce ordering between
+ * TestSetPageLocked(), the second mb is necessary to enforce ordering between
  * the clear_bit and the read of the waitqueue (to avoid SMP races with a
  * parallel wait_on_page_locked()).
  */

@@ -16,6 +16,6 @@ obj-y	 := memory.o mmap.o filemap.o mpro
 	    vmalloc.o slab.o bootmem.o swap.o vmscan.o page_io.o \
 	    page_alloc.o swap_state.o swapfile.o numa.o oom_kill.o \
 	    shmem.o highmem.o mempool.o msync.o mincore.o readahead.o \
-	    pdflush.o page-writeback.o
+	    pdflush.o page-writeback.o rmap.o
 
 include $(TOPDIR)/Rules.make

@@ -46,6 +46,7 @@
 #include <linux/pagemap.h>
 
 #include <asm/pgalloc.h>
+#include <asm/rmap.h>
 #include <asm/uaccess.h>
 #include <asm/tlb.h>
 #include <asm/tlbflush.h>

@@ -79,7 +80,7 @@ struct page *mem_map;
  */
 static inline void free_one_pmd(mmu_gather_t *tlb, pmd_t * dir)
 {
-	struct page *pte;
+	struct page *page;
 
 	if (pmd_none(*dir))
 		return;

@@ -88,9 +89,10 @@ static inline void free_one_pmd(mmu_gath
 		pmd_clear(dir);
 		return;
 	}
-	pte = pmd_page(*dir);
+	page = pmd_page(*dir);
 	pmd_clear(dir);
-	pte_free_tlb(tlb, pte);
+	pgtable_remove_rmap(page);
+	pte_free_tlb(tlb, page);
 }
 
 static inline void free_one_pgd(mmu_gather_t *tlb, pgd_t * dir)

@@ -150,6 +152,7 @@ pte_t * pte_alloc_map(struct mm_struct *
 			pte_free(new);
 			goto out;
 		}
+		pgtable_add_rmap(new, mm, address);
 		pmd_populate(mm, pmd, new);
 	}
 out:

@@ -177,6 +180,7 @@ pte_t * pte_alloc_kernel(struct mm_struc
 			pte_free_kernel(new);
 			goto out;
 		}
+		pgtable_add_rmap(virt_to_page(new), mm, address);
 		pmd_populate_kernel(mm, pmd, new);
 	}
 out:

@@ -260,10 +264,13 @@ skip_copy_pte_range:		address = (address
 
 				if (pte_none(pte))
 					goto cont_copy_pte_range_noset;
+				/* pte contains position in swap, so copy. */
 				if (!pte_present(pte)) {
 					swap_duplicate(pte_to_swp_entry(pte));
-					goto cont_copy_pte_range;
+					set_pte(dst_pte, pte);
+					goto cont_copy_pte_range_noset;
 				}
+				ptepage = pte_page(pte);
 				pfn = pte_pfn(pte);
 				if (!pfn_valid(pfn))
 					goto cont_copy_pte_range;

@@ -272,7 +279,7 @@ skip_copy_pte_range:		address = (address
 					goto cont_copy_pte_range;
 
 				/* If it's a COW mapping, write protect it both in the parent and the child */
-				if (cow && pte_write(pte)) {
+				if (cow) {
 					ptep_set_wrprotect(src_pte);
 					pte = *src_pte;
 				}

@@ -285,6 +292,7 @@ skip_copy_pte_range:		address = (address
 				dst->rss++;
 
 cont_copy_pte_range:		set_pte(dst_pte, pte);
+				page_add_rmap(ptepage, dst_pte);
 cont_copy_pte_range_noset:	address += PAGE_SIZE;
 				if (address >= end) {
 					pte_unmap_nested(src_pte);

@@ -342,6 +350,7 @@ static void zap_pte_range(mmu_gather_t *
 					if (pte_dirty(pte))
 						set_page_dirty(page);
 					tlb->freed++;
+					page_remove_rmap(page, ptep);
 					tlb_remove_page(tlb, page);
 				}
 			}

@@ -992,7 +1001,9 @@ static int do_wp_page(struct mm_struct *
 	if (pte_same(*page_table, pte)) {
 		if (PageReserved(old_page))
 			++mm->rss;
+		page_remove_rmap(old_page, page_table);
 		break_cow(vma, new_page, address, page_table);
+		page_add_rmap(new_page, page_table);
 		lru_cache_add(new_page);
 
 		/* Free the old page.. */

@@ -1199,6 +1210,7 @@ static int do_swap_page(struct mm_struct
 	flush_page_to_ram(page);
 	flush_icache_page(vma, page);
 	set_pte(page_table, pte);
+	page_add_rmap(page, page_table);
 
 	/* No need to invalidate - it was non-present before */
 	update_mmu_cache(vma, address, pte);

@@ -1215,14 +1227,13 @@ static int do_swap_page(struct mm_struct
 static int do_anonymous_page(struct mm_struct * mm, struct vm_area_struct * vma, pte_t *page_table, pmd_t *pmd, int write_access, unsigned long addr)
 {
 	pte_t entry;
+	struct page * page = ZERO_PAGE(addr);
 
 	/* Read-only mapping of ZERO_PAGE. */
 	entry = pte_wrprotect(mk_pte(ZERO_PAGE(addr), vma->vm_page_prot));
 
 	/* ..except if it's a write access */
 	if (write_access) {
-		struct page *page;
-
 		/* Allocate our own private page. */
 		pte_unmap(page_table);
 		spin_unlock(&mm->page_table_lock);

@@ -1248,6 +1259,7 @@ static int do_anonymous_page(struct mm_s
 	}
 
 	set_pte(page_table, entry);
+	page_add_rmap(page, page_table); /* ignores ZERO_PAGE */
 	pte_unmap(page_table);
 
 	/* No need to invalidate - it was non-present before */

@@ -1327,6 +1339,7 @@ static int do_no_page(struct mm_struct *
 		if (write_access)
 			entry = pte_mkwrite(pte_mkdirty(entry));
 		set_pte(page_table, entry);
+		page_add_rmap(new_page, page_table);
 		pte_unmap(page_table);
 	} else {
 		/* One of our sibling threads was faster, back out. */

@@ -68,8 +68,14 @@ static inline int copy_one_pte(struct mm
 {
 	int error = 0;
 	pte_t pte;
+	struct page * page = NULL;
+
+	if (pte_present(*src))
+		page = pte_page(*src);
 
 	if (!pte_none(*src)) {
+		if (page)
+			page_remove_rmap(page, src);
 		pte = ptep_get_and_clear(src);
 		if (!dst) {
 			/* No dest?  We must put it back. */

@@ -77,6 +83,8 @@ static inline int copy_one_pte(struct mm
 			error++;
 		}
 		set_pte(dst, pte);
+		if (page)
+			page_add_rmap(page, dst);
 	}
 	return error;
 }

@@ -92,6 +92,7 @@ static void __free_pages_ok (struct page
 	BUG_ON(PageLRU(page));
 	BUG_ON(PageActive(page));
 	BUG_ON(PageWriteback(page));
+	BUG_ON(page->pte_chain != NULL);
 	if (PageDirty(page))
 		ClearPageDirty(page);
 	BUG_ON(page_count(page) != 0);

@@ -383,6 +383,7 @@ static inline void unuse_pte(struct vm_a
 		return;
 	get_page(page);
 	set_pte(dir, pte_mkold(mk_pte(page, vma->vm_page_prot)));
+	page_add_rmap(page, dir);
 	swap_free(entry);
 	++vma->vm_mm->rss;
 }

.

On Tue, Jul 16, 2002 at 10:29:14PM -0700, Andrew Morton wrote:

I'm puzzling over this difference:

is no longer true for 2.5 (although it is still true for 2.4.)

Russell King ([email protected])                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Then I guess I messed up the ARM rmap.h for 2.5.

I knew it had to be different than the 2.4 one somehow and was under the impression that you changed the pagetable layout in 2.5 to have "4 kB page tables" with 2 kB hardware and 2 kB software page tables in the same page.

The page->mm thing is a stupid, stupid typo.

I guess akpm didn't have an ARM machine for testing, either ;)

regards,

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Will look into this soon.

And probably into this, if it turns out that we're wasting too much memory in no longer used pte_chains in real workloads, which will probably happen ;)

Rmap for 2.4 also has some code which could be used for this.

Benchmarky loads without a working set probably aren't all that suitable for evaluating page replacement. VM (and general caching) works _because_ of the working set property.

Does anybody know of a working set simulator we could use to test things like this ?

That's the "minimal" part of "minimal rmap" ;))

Ed Tomlinson has some code for 11), which should be mergeable soon. In combination with changed page replacement priorities we'll be able to make sure updatedb won't evict everything.

The importance of rmap here is making sure we're _able_ to do this kind of tuning instead of tweaking the same magic knobs we've (unsuccessfully) tweaked in the last 8 years.

regards,

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

That is not a problem with rmap per se, it's a result of not properly handling streaming IO. I don't think you want to get bogged down in this detail at the moment, it will only distract from the real issues. My recommendation is to just pretend for the time being that this is correct behaviour.

On the other hand, if updatedb is pushing you into swap, that's a bug.

Daniel

A good argument for an O_STREAM... various semantics we can modify for it.

Robert Love

It can be fixed in kernel too, it's just that the effort would be poorly spent at this point. This is in roughly the same category as process-level paging policy: yes, if it's implemented properly the VM appears to work better and users will post nice things on lkml about it, but it's a red herring. Such adjustments are better left for later in the cycle, when the smoke has cleared from the basic merge, and benchmarks should focus narrowly on behaviour that is actually affected by the change in scanning strategy.

Daniel

I don't agree with this, for a very simple reason.

The current rmap patch was created in order to change the VM behaviour as little as possible and ONLY provide an infrastructure. Benchmarking a completely untuned thing that was built to not change anything is bound to give meaningless results.

I say we _use_ the infrastructure that akpm is trying to get merged now in order to implement something useful.

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

I do agree with Rik here. Once the basic rmap infrastructure is merged we need to work on implementing stuff on top of it or else there is no point.

If we cannot show the infrastructure is useful, then Linus will surely rip rmap out of the kernel in time.

Summary: once it is in and seems correct we need to start providing (in _pieces_) parts from Rik's full rmap patch and other VM-related code for 2.5 to see where rmap can take us...

Robert Love

Well then we all agree, because that's just what I said.

Daniel

I (mis)took "later in the cycle" and "when the smoke has cleared" as a bit away - whereas my "once it is merged" to be, oh, by next week.

Robert Love

Umm, updatedb isn't exactly streaming...

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

You're right, it's not exactly, it's hitting every directory entry on the system, hopefully just once. Let's not call it streaming, let's call it... err... use-once? ;-)

Daniel

                                                     ^^^^^^^^^^^^^^^

Nope. If it hits every directory entry once, it'll hit every page with directory or inode information multiple times, causing that page to enter the active list and push out process pages.

This is exactly what we want to prevent.

regards,

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Yes, it could get challenging, but it's very desirable to do the optimization somehow. It's even more desirable to stay focussed on the immediate issues, imho.

Food for thought: readdir actually picks up the entries 4K-worth at a time, however that's randomly aligned with respect to directory block boundaries, meaning that most blocks get two hits, which could well be the problem.

Inode table blocks present a more difficult problem. It's really hard to know when to evict them, and just arbitrarily holding them to a certain percentage of memory isn't nice either.

I think Andrew also mentioned he sees a lot of buffers sitting around in the morning. His strip-buffers-immediately hack would kill that one dead.

Daniel

One simple way of getting this right is adding a new list to the VM, after which we'd have the following lists:

1) new_pages list, restricted to a certain size (5% of RAM, 50% of the size of the inactive list, ...) FIFO, new pages get added to the front of the list, old pages get their accessed bit cleared and moved to the inactive list

2) inactive list, second chance fifo, target size 1/2 of active list ? pages sit on the inactive list until the pageout code runs into them, if the page was not accessed it will be evicted, if it was accessed it will be moved to the active list

3) active list, second chance fifo
pages on this list get rotated slowly, if they were referenced they go back on the other side of the list, if they were not referenced they go to the inactive list

With this setup, we should be able to catch things like updatedb and common streaming IO; their accesses to the pages should mostly happen while the pages are on the new_pages list (1) and they shouldn't get referenced again while on the inactive list.

Of course, this isn't the case for things like the directory /usr, but we _want_ to cache directories close to the top of the tree anyway. Besides, we won't have many of those directories.

An added advantage of this scheme is that we'll no longer need to touch the lru list in mark_page_accessed() (reducing contention) and use-once might actually work for mmap()d pages.

regards,

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Yes, I've always felt that at least one new list is needed to do the job properly, and there are other considerations as well. What we really want to do is treat a short burst of accesses to a page as a single access. Right now we're only doing a very crude approximation of that, which happens to work for some common situations, of which updatedb is not one.

Obviously we don't want to be adding new lists and other experimental cruft just now.

Daniel

I know it's against a long-standing tradition, but I'd really like to get changes like this in _before_ the code change.

regards,

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Code _freeze_ that is, duh.

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Is the halloween freeze a code freeze? I thought it was a feature freeze.

Daniel

It is, but changing the way the VM works is also something that should be done before a feature freeze. After the freeze we really shouldn't "innovate" a lot and spend more time tweaking whatever we have into perfection.

regards,

Rik

Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Your thinking is correct. No new features after halloween, but obviously code *fixing* those that made it before the cut-off will still be taken right up to 2.6.0

I have visions of pre-freeze October as everyone goes mad rushing to get their last minute features in, and then post-freeze November the endless. "No really, it's just a fix!" mails.

Fun times lie ahead.

Dave

| Dave Jones.        http://www.codemonkey.org.uk
| SuSE Labs

No, you are right. The idea was for it to be a feature freeze. I would expect the code freeze n years^Wmonths later just prior to 2.6.0's release.

Robert Love

Nope. It was all inodes and dentries.

`buffermem' accounting went away in 2.5 altogether. And the zillions-of-buffer_heads problems should be greatly improved because a) they're half the size of 2.4's bhs and b) we no longer attach buffer_heads for reads.

-

Similar properties that warrant similar behavior, though - specifically, cache and swap behavior ideally would be use-once.

Robert Love