vmtrace

Hi,

The sequence of pages which a given process or workload accesses during its lifetime, a.k.a. "reference trace", is very important information.

It has been used in the past for comparison of page replacement algorithms and other optimizations.

We've been talking on IRC on how to generate reference traces for memory accesses, and a suggestion came up to periodically unmap all present pte's of a given process. The following patch implements a "kptecleaner" thread which is woken at a certain interval (hardcoded to HZ/2 at present) which does that, copying the pte walking functions from zap_pte_range().

Note: The patch lacks "pte_disable"/"pte_enable" macro pair (those are supposed to operate on a free bit in the flags field of the page table which was defined as PTE_DISABLE) and "pte_presprotect" macro to disable the PTE_PRESENT bit. I had that written down but _I LOST MY LAPTOP_ with the complete patch inside :(

Here is how the patch works: You write the target UID into /proc/vmtrace_uid and the "kptecleaner" thread begins disabling the present bit of every pte for all processes for the target UID. The pagefault path records the addresses via relayfs.

Here is is the plotting of virtual time versus user address for a few programs:

compilation of a small C file with gcc
http://master.kernel.org/~marcelo/gcc.png

And with crippled disabling of pte's (thats why the text accesses are not present: because refaulting was not being catch, but still interesting data in that one can see the sequential nature of memory accesses by these programs).

mmap002 from "memtest"
http://master.kernel.org/~marcelo/mmap002.png

"qsbench"
http://master.kernel.org/~marcelo/qsbench.png

Scott Kaplan wrote a much more complete patch for v2.4 to record memory accesses (along with read/write syscalls, and others) and generate a reference trace. http://www.cs.amherst.edu/~sfkaplan/research/kVMTrace/

Scott, do you have any plans to port your work to v2.6? Relayfs (present in recent v2.6 kernels) implements a mechanism to send data to userspace which is very convenient.

diff -Nur --exclude-from=/home/marcelo/excl linux-2.6.13.orig/include/linux/vmtrace.h linux-2.6.13/include/linux/vmtrace.h
@@ -0,0 +1,11 @@
+
+struct vm_trace_entry {
+	unsigned long inode;
+	unsigned long bdev;
+	unsigned long offset;
+	unsigned long len;
+	unsigned long prot;
+	pid_t pid;
+	unsigned long tstamp;
+};
+

diff -Nur --exclude-from=/home/marcelo/excl linux-2.6.13.orig/mm/Makefile linux-2.6.13/mm/Makefile
@@ -20,3 +20,4 @@
 obj-$(CONFIG_TINY_SHMEM) += tiny-shmem.o
 obj-$(CONFIG_MEMORY_HOTPLUG) += memory_hotplug.o
 obj-$(CONFIG_FS_XIP) += filemap_xip.o
+obj-$(CONFIG_VMTRACE) += vmtrace.o

diff -Nur --exclude-from=/home/marcelo/excl linux-2.6.13.orig/mm/memory.c linux-2.6.13/mm/memory.c
@@ -351,7 +351,7 @@
 	unsigned long pfn;
 
 	/* pte contains position in swap or file, so copy. */
-	if (unlikely(!pte_present(pte))) {
+	if (unlikely(!pte_present(pte)) && !pte_disabled(pte)) {
 		if (!pte_file(pte)) {
 			swap_duplicate(pte_to_swp_entry(pte));
 			/* make sure dst_mm is on swapoff's mmlist. */

@@ -536,7 +536,7 @@
 		pte_t ptent = *pte;
 		if (pte_none(ptent))
 			continue;
-		if (pte_present(ptent)) {
+		if (pte_present(ptent) || pte_disabled(ptent)) {
 			struct page *page = NULL;
 			unsigned long pfn = pte_pfn(ptent);
 			if (pfn_valid(pfn)) {

@@ -579,7 +579,7 @@
 			else if (pte_young(ptent))
 				mark_page_accessed(page);
 			tlb->freed++;
-			page_remove_rmap(page);
+			__page_remove_rmap(page, ptent);
 			tlb_remove_page(tlb, page);
 			continue;
 		}

@@ -2004,6 +2004,15 @@
 
 	entry = *pte;
 	if (!pte_present(entry)) {
+		vmtrace(vma, address);
+		if (pte_disabled(entry)) {
+			set_pte_at(vma->vm_mm, address, pte, pte_enable(pte_mkpresent(entry)));
+			flush_tlb_page(vma, address);
+			update_mmu_cache(vma, address, entry);
+			pte_unmap(pte);
+			spin_unlock(&mm->page_table_lock);
+			return VM_FAULT_MINOR;
+		}
 		/*
 		 * If it truly wasn't present, we know that kswapd
 		 * and the PTE updates will not touch it later. So

diff -Nur --exclude-from=/home/marcelo/excl linux-2.6.13.orig/mm/page_alloc.c linux-2.6.13/mm/page_alloc.c
@@ -122,13 +122,19 @@
 	return 0;
 }
 
-static void bad_page(const char *function, struct page *page)
+
+void dump_page(struct page *page, char *function)
 {
 	printk(KERN_EMERG "Bad page state at %s (in process '%s', page %p)\n",
 		function, current->comm, page);
 	printk(KERN_EMERG "flags:0x%0*lx mapping:%p mapcount:%d count:%d\n",
 		(int)(2*sizeof(page_flags_t)), (unsigned long)page->flags,
 		page->mapping, page_mapcount(page), page_count(page));
+}
+
+static void bad_page(const char *function, struct page *page)
+{
+	dump_page(page, function);
 	printk(KERN_EMERG "Backtrace:\n");
 	dump_stack();
 	printk(KERN_EMERG "Trying to fix it up, but a reboot is needed\n");

diff -Nur --exclude-from=/home/marcelo/excl linux-2.6.13.orig/mm/rmap.c linux-2.6.13/mm/rmap.c
@@ -477,18 +477,32 @@
 		inc_page_state(nr_mapped);
 }
 
+void page_remove_rmap(struct page * page)
+{
+	__page_remove_rmap(page, NULL);
+}
+
+void dump_pte(pte_t pte)
+{
+	printk(KERN_ERR "pte.low:%lx\n", pte.pte_low);
+}
+
 /**
  * page_remove_rmap - take down pte mapping from a page
  * @page: page to remove mapping from
  *
  * Caller needs to hold the mm->page_table_lock.
  */
-void page_remove_rmap(struct page *page)
+void __page_remove_rmap(struct page *page, pte_t pte)
 {
 	BUG_ON(PageReserved(page));
 
 	if (atomic_add_negative(-1, &page->_mapcount)) {
-		BUG_ON(page_mapcount(page) < 0);
+		if (page_mapcount(page) < 0) {
+			dump_page(page, "__page_remove_rmap");
+			dump_pte(pte);
+			BUG();
+		}
 		/*
 		 * It would be tidy to reset the PageAnon mapping here,
 		 * but that might overwrite a racing page_add_anon_rmap

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

Hello Marcelo (and everyone on linux-mm),

There are known accuracy limitations to this approach. Most importantly, during any phase change, if you don't unmap the present PTE's often enough, you will introduce substantial error into any simulations that use these traces.

Ugh! Sorry to hear that. I do have my own PTE_DISABLE and PTE_ENABLE in the kVMTrace patch that should be easy to extract. Note, though, that I found it necessary to use two bits -- one to denote a PTE disabled by the trace-gathering mechanism, and one to denote a PTE disabled by a user-level mprotect() request. This differentiation is necessary for correctness.

If by ``plans'' you mean ``desire'', then yes; if you mean ``an organized timeline'', then no. I must say, though, that the relayfs sounds as though it will make the porting much easier, allowing me to strip out the ad-hoc in-kernel logging mechanism that I use in the 2.4-based kVMTrace.

I'm using kVMTrace actively to drive some research. If there's a demand for a 2.6-based version of it, then I'm certainly interested in porting it forward, *especially* if there's anyone out there who would like to help me along! :-) Most of the hard work isn't in the kernel -- that portion is simple. The bulk of the work is in the post-processing utility that reconstructs the state of every task in order to attribute each reference to the task that performed it and to identify all uses of shared memory. I am hopeful, though, that the changes from 2.4 to 2.6 won't be all that onerous in this respect.

Scott