freemaps

["Frederic Rossi (LMC)" <Frederic.Rossi@ericsson.ca>]

[-- Attachment #1: Type: text/plain, Size: 2086 bytes --]

Hi,

This patch is intended to provide better support for allocations done with
mmap. As mentioned by Ingo Molnar, keeping the last hole doesn't save us
from scanning vmas because of size constraint.

The following patch implements a simple scheme. The goal is to quickly
return virtual addresses but without scanning the address space at all. It
also works for fixed mappings by reserving areas of virtual addresses.

A global (per mm) cache is maintained from which we can peek ranges of
addresses. There is no link towards vmas. When addresses are cached out they
are simply forgotten. It is then up to the vma users to explicitly cache
out/back areas.

Two of the main functions used for allocations are:

vma_cache_detach(len) returns the first available range of this length
starting from the first block in the cache. The overhead is still very low
since only the cache is scanned (using a first-fit scheme).

vma_cache_area(addr, len) is used to reserve an area from addr to addr+len.
This gives also the possibility to reserve in advance a bunch of virtual
addresses without explicitly mapping them.

Caches are also accessible from /proc/<pid>/freemaps showing free areas
along with their length. Applications willing to map to fixed addresses can
check what is available before doing a mmap().

I guess it could probably give more control on the fragmentation of the
virtual address space too. I successfully ran this patch in a desktop
environment. I also did some simple testing to see how get_unmapped_area()
reacts. Running the kernel 2.5.50 I get
100000 mmaps, mmap=2545 msec munmap=59 msec
100000 mmaps, mmap=2545 msec munmap=58 msec
100000 mmaps, mmap=2544 msec munmap=60 msec
100000 mmaps, mmap=2547 msec munmap=60 msec

and with freemaps I get
100000 mmaps, mmap=79 msec munmap=60 msec
100000 mmaps, mmap=79 msec munmap=60 msec
100000 mmaps, mmap=80 msec munmap=60 msec
100000 mmaps, mmap=79 msec munmap=60 msec

Since there is quite an amazing difference I really would like to have your
comments on this.

I joined a patch against 2.5.50.

Regards,
Frederic







[-- Attachment #2: freemaps-2.5.50-p4.patch --]
[-- Type: application/octet-stream, Size: 24750 bytes --]

diff --exclude=RCS -BbNur linux-2.5.50/fs/binfmt_aout.c linux-2.5.50~/fs/binfmt_aout.c
--- linux-2.5.50/fs/binfmt_aout.c	Wed Nov 27 17:35:51 2002
+++ linux-2.5.50~/fs/binfmt_aout.c	Thu Dec 12 14:51:05 2002
@@ -24,6 +24,7 @@
 #include <linux/binfmts.h>
 #include <linux/personality.h>
 #include <linux/init.h>
+#include <linux/vma_cache.h>
 
 #include <asm/system.h>
 #include <asm/uaccess.h>
@@ -307,7 +308,8 @@
 		(current->mm->start_data = N_DATADDR(ex));
 	current->mm->brk = ex.a_bss +
 		(current->mm->start_brk = N_BSSADDR(ex));
-	current->mm->free_area_cache = TASK_UNMAPPED_BASE;
+
+	vma_cache_init (current->mm);
 
 	current->mm->rss = 0;
 	current->mm->mmap = NULL;
diff --exclude=RCS -BbNur linux-2.5.50/fs/binfmt_elf.c linux-2.5.50~/fs/binfmt_elf.c
--- linux-2.5.50/fs/binfmt_elf.c	Wed Nov 27 17:35:59 2002
+++ linux-2.5.50~/fs/binfmt_elf.c	Thu Dec 12 14:51:05 2002
@@ -35,6 +35,7 @@
 #include <linux/compiler.h>
 #include <linux/highmem.h>
 #include <linux/pagemap.h>
+#include <linux/vma_cache.h>
 
 #include <asm/uaccess.h>
 #include <asm/param.h>
@@ -617,7 +618,9 @@
 	/* Do this so that we can load the interpreter, if need be.  We will
 	   change some of these later */
 	current->mm->rss = 0;
-	current->mm->free_area_cache = TASK_UNMAPPED_BASE;
+ 	
+ 	vma_cache_init (current->mm);
+
 	retval = setup_arg_pages(bprm);
 	if (retval < 0) {
 		send_sig(SIGKILL, current, 0);
diff --exclude=RCS -BbNur linux-2.5.50/fs/proc/array.c linux-2.5.50~/fs/proc/array.c
--- linux-2.5.50/fs/proc/array.c	Wed Nov 27 17:36:05 2002
+++ linux-2.5.50~/fs/proc/array.c	Thu Dec 12 14:51:05 2002
@@ -73,6 +73,7 @@
 #include <linux/highmem.h>
 #include <linux/file.h>
 #include <linux/times.h>
+#include <linux/vma_cache.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
@@ -513,6 +514,99 @@
 	return len;
 }
 
+ssize_t proc_pid_read_vmc (struct task_struct *task, struct file * file, char * buf, size_t count, loff_t *ppos)
+{
+	struct mm_struct *mm;
+	struct vm_area_struct * map;
+	char *tmp, *kbuf;
+	long retval;
+	int off, lineno, loff;
+	struct list_head *h;
+
+	/* reject calls with out of range parameters immediately */
+	retval = 0;
+	if (*ppos > LONG_MAX)
+		goto out;
+	if (count == 0)
+		goto out;
+	off = (long)*ppos;
+	/*
+	 * We might sleep getting the page, so get it first.
+	 */
+	retval = -ENOMEM;
+	kbuf = (char*)__get_free_page(GFP_KERNEL);
+	if (!kbuf)
+		goto out;
+
+	tmp = (char*)__get_free_page(GFP_KERNEL);
+	if (!tmp)
+		goto out_free1;
+
+	task_lock(task);
+	mm = task->mm;
+	if (mm)
+		atomic_inc(&mm->mm_users);
+	task_unlock(task);
+	retval = 0;
+	if (!mm)
+		goto out_free2;
+
+	down_read(&mm->mmap_sem);
+	map = mm->mmap;
+	lineno = 0;
+	loff = 0;
+	if (count > PAGE_SIZE)
+		count = PAGE_SIZE;
+
+	list_for_each (h, &mm->vma_cache_head) {
+		struct vma_cache_struct *vmc = list_entry (h, struct vma_cache_struct, head);
+		
+		int len;
+		if (off > PAGE_SIZE) {
+			off -= PAGE_SIZE;
+			goto next;
+		}
+
+		len = sprintf (tmp, "%lx-%lx %lu\n", vmc->vm_start, vmc->vm_end, vmc->vm_end-vmc->vm_start);
+		len -= off;
+		if (len > 0) {
+			if (retval+len > count) {
+				/* only partial line transfer possible */
+				len = count - retval;
+				/* save the offset where the next read
+				 * must start */
+				loff = len+off;
+			}
+			memcpy(kbuf+retval, tmp+off, len);
+			retval += len;
+		}
+		off = 0;
+next:
+		if (!loff)
+			lineno++;
+		if (retval >= count)
+			break;
+		if (loff) BUG();
+		map = map->vm_next;
+	}
+
+	up_read(&mm->mmap_sem);
+	mmput(mm);
+
+	if (retval > count) BUG();
+	if (copy_to_user(buf, kbuf, retval))
+		retval = -EFAULT;
+	else
+		*ppos = (lineno << PAGE_SHIFT) + loff;
+
+out_free2:
+	free_page((unsigned long)tmp);
+out_free1:
+	free_page((unsigned long)kbuf);
+out:
+	return retval;
+}
+
 ssize_t proc_pid_read_maps (struct task_struct *task, struct file * file, char * buf,
 			  size_t count, loff_t *ppos)
 {
diff --exclude=RCS -BbNur linux-2.5.50/fs/proc/base.c linux-2.5.50~/fs/proc/base.c
--- linux-2.5.50/fs/proc/base.c	Wed Nov 27 17:36:06 2002
+++ linux-2.5.50~/fs/proc/base.c	Thu Dec 12 14:51:05 2002
@@ -54,6 +54,7 @@
 	PROC_PID_CMDLINE,
 	PROC_PID_STAT,
 	PROC_PID_STATM,
+	PROC_PID_VMC,
 	PROC_PID_MAPS,
 	PROC_PID_MOUNTS,
 	PROC_PID_WCHAN,
@@ -75,6 +76,7 @@
   E(PROC_PID_CMDLINE,	"cmdline",	S_IFREG|S_IRUGO),
   E(PROC_PID_STAT,	"stat",		S_IFREG|S_IRUGO),
   E(PROC_PID_STATM,	"statm",	S_IFREG|S_IRUGO),
+  E(PROC_PID_VMC,	"freemaps",	S_IFREG|S_IRUGO),
   E(PROC_PID_MAPS,	"maps",		S_IFREG|S_IRUGO),
   E(PROC_PID_MEM,	"mem",		S_IFREG|S_IRUSR|S_IWUSR),
   E(PROC_PID_CWD,	"cwd",		S_IFLNK|S_IRWXUGO),
@@ -99,6 +101,7 @@
 }
 
 ssize_t proc_pid_read_maps(struct task_struct*,struct file*,char*,size_t,loff_t*);
+ssize_t proc_pid_read_vmc(struct task_struct*,struct file*,char*,size_t,loff_t*);
 int proc_pid_stat(struct task_struct*,char*);
 int proc_pid_status(struct task_struct*,char*);
 int proc_pid_statm(struct task_struct*,char*);
@@ -336,6 +339,21 @@
 	.read		= pid_maps_read,
 };
 
+static ssize_t pid_vmc_read(struct file * file, char * buf,
+			      size_t count, loff_t *ppos)
+{
+	struct inode * inode = file->f_dentry->d_inode;
+	struct task_struct *task = proc_task(inode);
+	ssize_t res;
+
+	res = proc_pid_read_vmc (task, file, buf, count, ppos);
+	return res;
+}
+
+static struct file_operations proc_vmc_operations = {
+	read:		pid_vmc_read,
+};
+
 extern struct seq_operations mounts_op;
 static int mounts_open(struct inode *inode, struct file *file)
 {
@@ -1023,6 +1041,9 @@
 			inode->i_fop = &proc_info_file_operations;
 			ei->op.proc_read = proc_pid_statm;
 			break;
+		case PROC_PID_VMC:
+			inode->i_fop = &proc_vmc_operations;
+			break;
 		case PROC_PID_MAPS:
 			inode->i_fop = &proc_maps_operations;
 			break;
diff --exclude=RCS -BbNur linux-2.5.50/include/linux/init_task.h linux-2.5.50~/include/linux/init_task.h
--- linux-2.5.50/include/linux/init_task.h	Wed Nov 27 17:35:49 2002
+++ linux-2.5.50~/include/linux/init_task.h	Thu Dec 12 14:51:05 2002
@@ -41,6 +41,7 @@
 	.page_table_lock =  SPIN_LOCK_UNLOCKED, 		\
 	.mmlist		= LIST_HEAD_INIT(name.mmlist),		\
 	.default_kioctx = INIT_KIOCTX(name.default_kioctx, name),	\
+        .vma_cache_head = LIST_HEAD_INIT(name.vma_cache_head),  \
 }
 
 #define INIT_SIGNALS(sig) {	\
diff --exclude=RCS -BbNur linux-2.5.50/include/linux/sched.h linux-2.5.50~/include/linux/sched.h
--- linux-2.5.50/include/linux/sched.h	Wed Nov 27 17:35:49 2002
+++ linux-2.5.50~/include/linux/sched.h	Thu Dec 12 14:51:05 2002
@@ -172,11 +172,16 @@
 
 #include <linux/aio.h>
 
+struct vma_cache_struct {
+	struct list_head head;
+	unsigned long vm_start;
+	unsigned long vm_end;
+};
+
 struct mm_struct {
 	struct vm_area_struct * mmap;		/* list of VMAs */
 	struct rb_root mm_rb;
 	struct vm_area_struct * mmap_cache;	/* last find_vma result */
-	unsigned long free_area_cache;		/* first hole */
 	pgd_t * pgd;
 	atomic_t mm_users;			/* How many users with user space? */
 	atomic_t mm_count;			/* How many references to "struct mm_struct" (users count as 1) */
@@ -189,6 +194,8 @@
 						 * by mmlist_lock
 						 */
 
+        struct list_head vma_cache_head;        /* cache for free virtual address areas */
+
 	unsigned long start_code, end_code, start_data, end_data;
 	unsigned long start_brk, brk, start_stack;
 	unsigned long arg_start, arg_end, env_start, env_end;
diff --exclude=RCS -BbNur linux-2.5.50/include/linux/slab.h linux-2.5.50~/include/linux/slab.h
--- linux-2.5.50/include/linux/slab.h	Wed Nov 27 17:36:23 2002
+++ linux-2.5.50~/include/linux/slab.h	Thu Dec 12 14:51:05 2002
@@ -65,6 +65,7 @@
 extern int FASTCALL(kmem_cache_reap(int));
 
 /* System wide caches */
+extern kmem_cache_t	*vma_cache_cachep;
 extern kmem_cache_t	*vm_area_cachep;
 extern kmem_cache_t	*mm_cachep;
 extern kmem_cache_t	*names_cachep;
diff --exclude=RCS -BbNur linux-2.5.50/include/linux/vma_cache.h linux-2.5.50~/include/linux/vma_cache.h
--- linux-2.5.50/include/linux/vma_cache.h	Wed Dec 31 19:00:00 1969
+++ linux-2.5.50~/include/linux/vma_cache.h	Thu Dec 12 14:51:05 2002
@@ -0,0 +1,25 @@
+#ifndef _VMA_CACHE_H_
+#define _VMA_CACHE_H_
+
+#define VMA_CACHE_EMPTY(m,a)    (list_empty(&(a)->head))
+
+#define vma_cache_alloc()     (kmem_cache_alloc(vma_cache_cachep, GFP_KERNEL))
+#define vma_cache_free(v)                              \
+do {                                                   \
+        if (v) {                                       \
+                list_del_init (&(v)->head);            \
+                kmem_cache_free (vma_cache_cachep, v); \
+        }                                              \
+} while (0)
+
+int vma_cache_init (struct mm_struct *);
+struct vma_cache_struct *vma_cache_find (struct mm_struct *, unsigned long, int);
+void vma_cache_shtdn (struct mm_struct *);
+int vma_cache_attach (struct mm_struct *, unsigned long, int);
+int vma_cache_merge (struct mm_struct *, struct vma_cache_struct *, unsigned long, int);
+int vma_cache_clone (struct mm_struct *, struct mm_struct *);
+unsigned long vma_cache_area (struct mm_struct *, unsigned long, int);
+unsigned long vma_cache_detach (struct mm_struct *, int);
+
+#endif /* #ifndef _VMA_CACHE_H_ */
+
diff --exclude=RCS -BbNur linux-2.5.50/kernel/exit.c linux-2.5.50~/kernel/exit.c
--- linux-2.5.50/kernel/exit.c	Wed Nov 27 17:36:18 2002
+++ linux-2.5.50~/kernel/exit.c	Thu Dec 12 14:51:05 2002
@@ -21,6 +21,7 @@
 #include <linux/ptrace.h>
 #include <linux/profile.h>
 #include <linux/mount.h>
+#include <linux/vma_cache.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
diff --exclude=RCS -BbNur linux-2.5.50/kernel/fork.c linux-2.5.50~/kernel/fork.c
--- linux-2.5.50/kernel/fork.c	Wed Nov 27 17:35:49 2002
+++ linux-2.5.50~/kernel/fork.c	Thu Dec 12 14:51:05 2002
@@ -29,6 +29,7 @@
 #include <linux/futex.h>
 #include <linux/ptrace.h>
 #include <linux/mount.h>
+#include <linux/vma_cache.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -215,10 +216,10 @@
 
 	down_write(&oldmm->mmap_sem);
 	flush_cache_mm(current->mm);
+	vma_cache_init (mm);
 	mm->locked_vm = 0;
 	mm->mmap = NULL;
 	mm->mmap_cache = NULL;
-	mm->free_area_cache = TASK_UNMAPPED_BASE;
 	mm->map_count = 0;
 	mm->rss = 0;
 	mm->cpu_vm_mask = 0;
@@ -246,6 +247,7 @@
 				goto fail_nomem;
 			charge += len;
 		}
+		vma_cache_area (mm, mpnt->vm_start, mpnt->vm_end-mpnt->vm_start);
 		tmp = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
 		if (!tmp)
 			goto fail_nomem;
@@ -334,7 +336,7 @@
 	mm->page_table_lock = SPIN_LOCK_UNLOCKED;
 	mm->ioctx_list_lock = RW_LOCK_UNLOCKED;
 	mm->default_kioctx = (struct kioctx)INIT_KIOCTX(mm->default_kioctx, *mm);
-	mm->free_area_cache = TASK_UNMAPPED_BASE;
+	vma_cache_init (mm);
 
 	if (likely(!mm_alloc_pgd(mm)))
 		return mm;
@@ -381,6 +383,7 @@
 		mmlist_nr--;
 		spin_unlock(&mmlist_lock);
 		exit_mmap(mm);
+		vma_cache_shtdn(mm);
 		mmdrop(mm);
 	}
 }
@@ -1054,6 +1057,9 @@
 /* SLAB cache for mm_struct structures (tsk->mm) */
 kmem_cache_t *mm_cachep;
 
+/* SLAB cache for vma_cache structures */
+kmem_cache_t *vma_cache_cachep;
+
 void __init proc_caches_init(void)
 {
 	sigact_cachep = kmem_cache_create("signal_act",
@@ -1085,4 +1091,11 @@
 			SLAB_HWCACHE_ALIGN, NULL, NULL);
 	if(!mm_cachep)
 		panic("vma_init: Cannot alloc mm_struct SLAB cache");
+
+	vma_cache_cachep = kmem_cache_create("vma_cache_struct",
+			sizeof(struct vma_cache_struct), 0,
+			SLAB_HWCACHE_ALIGN, NULL, NULL);
+	if(!vm_area_cachep)
+		panic("vma_init: Cannot alloc vma_cache_struct SLAB cache");
+
 }
diff --exclude=RCS -BbNur linux-2.5.50/mm/Makefile linux-2.5.50~/mm/Makefile
--- linux-2.5.50/mm/Makefile	Wed Nov 27 17:36:14 2002
+++ linux-2.5.50~/mm/Makefile	Thu Dec 12 14:51:05 2002
@@ -8,7 +8,7 @@
 	    vmalloc.o slab.o bootmem.o swap.o vmscan.o page_alloc.o \
 	    oom_kill.o shmem.o highmem.o mempool.o msync.o mincore.o \
 	    readahead.o pdflush.o page-writeback.o rmap.o madvise.o \
-	    vcache.o truncate.o
+	    vcache.o truncate.o vma_cache.o
 
 obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o
 
diff --exclude=RCS -BbNur linux-2.5.50/mm/mmap.c linux-2.5.50~/mm/mmap.c
--- linux-2.5.50/mm/mmap.c	Wed Nov 27 17:36:06 2002
+++ linux-2.5.50~/mm/mmap.c	Thu Dec 12 14:51:05 2002
@@ -18,6 +18,7 @@
 #include <linux/security.h>
 #include <linux/hugetlb.h>
 #include <linux/profile.h>
+#include <linux/vma_cache.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgalloc.h>
@@ -514,6 +515,7 @@
 	if (vma && vma->vm_start < addr + len) {
 		if (do_munmap(mm, addr, len))
 			return -ENOMEM;
+		vma_cache_area (mm, addr, len);
 		goto munmap_back;
 	}
 
@@ -647,7 +649,6 @@
 {
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma;
-	int found_hole = 0;
 
 	if (len > TASK_SIZE)
 		return -ENOMEM;
@@ -657,25 +658,9 @@
 		vma = find_vma(mm, addr);
 		if (TASK_SIZE - len >= addr &&
 		    (!vma || addr + len <= vma->vm_start))
-			return addr;
-	}
-	addr = mm->free_area_cache;
-
-	for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
-		/* At this point:  (!vma || addr < vma->vm_end). */
-		if (TASK_SIZE - len < addr)
-			return -ENOMEM;
-		/*
-		 * Record the first available hole.
-		 */
-		if (!found_hole && (!vma || addr < vma->vm_start)) {
-			mm->free_area_cache = addr;
-			found_hole = 1;
-		}
-		if (!vma || addr + len <= vma->vm_start)
-			return addr;
-		addr = vma->vm_end;
+			return vma_cache_area (current->mm, addr, len);
 	}
+	return vma_cache_detach (current->mm, len);
 }
 #else
 extern unsigned long arch_get_unmapped_area(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
@@ -688,7 +673,7 @@
 			return -ENOMEM;
 		if (addr & ~PAGE_MASK)
 			return -EINVAL;
-		return addr;
+		return vma_cache_area (current->mm, addr, len);
 	}
 
 	if (file && file->f_op && file->f_op->get_unmapped_area)
@@ -962,13 +947,8 @@
 	area->vm_mm->total_vm -= len >> PAGE_SHIFT;
 	if (area->vm_flags & VM_LOCKED)
 		area->vm_mm->locked_vm -= len >> PAGE_SHIFT;
-	/*
-	 * Is this a new hole at the lowest possible address?
-	 */
-	if (area->vm_start >= TASK_UNMAPPED_BASE &&
-				area->vm_start < area->vm_mm->free_area_cache)
-	      area->vm_mm->free_area_cache = area->vm_start;
 
+	vma_cache_attach (mm, area->vm_start, area->vm_end-area->vm_start);
 	remove_shared_vm_struct(area);
 
 	if (area->vm_ops && area->vm_ops->close)
@@ -1336,7 +1316,6 @@
 		kmem_cache_free(vm_area_cachep, mpnt);
 		mpnt = next;
 	}
-		
 }
 
 /* Insert vm structure into process list sorted by address
diff --exclude=RCS -BbNur linux-2.5.50/mm/vma_cache.c linux-2.5.50~/mm/vma_cache.c
--- linux-2.5.50/mm/vma_cache.c	Wed Dec 31 19:00:00 1969
+++ linux-2.5.50~/mm/vma_cache.c	Fri Dec 13 08:52:52 2002
@@ -0,0 +1,364 @@
+/*
+ *  linux/mm/vma_cache.c
+ * 
+ *  These routines are used for the allocation of virtual memory areas. Each MM context is 
+ *  assigned a cache which contains virtual address ranges a process can allocate to map into 
+ *  its own address space. These routines assume the caller holds the global mm->mmap_sem.
+ *  Dec 2002, frederic.rossi@ericsson.ca
+ *
+ */
+
+#include <linux/slab.h>
+#include <linux/sched.h>
+#include <linux/errno.h>
+#include <linux/vma_cache.h>
+
+#define next_area(v) (list_entry ((v)->head.next, struct vma_cache_struct, head))
+#define prev_area(v) (list_entry ((v)->head.prev, struct vma_cache_struct, head))
+
+/* not mapped addresses */
+#define unmapped_addr(v,a)    ((a)>=(v)->vm_start && (a)<=(v)->vm_end)
+#define unmapped_area(v,a,l)  ((a)>=(v)->vm_start && (a)+(l)<=(v)->vm_end)
+#define unmapped_left(v,a,l)  ((a)+(l)<(v)->vm_start)
+#define unmapped_right(v,al)  ((a)>(v)->vm_end)
+
+/* partially mapped addresses */
+#define pmapped_left(v,a,l)   ((a)+(l)==(v)->vm_start)
+#define pmapped_right(v,a,l)  ((a)==(v)->vm_end)
+
+static __inline__ int vma_cache_isvalid (struct mm_struct *mm, unsigned long addr, int len)
+{
+	return (addr >= TASK_UNMAPPED_BASE && addr+len <= TASK_SIZE)? 1 : 0;
+}	
+
+static __inline__ int vma_cache_chainout (struct mm_struct *mm, struct vma_cache_struct *vmc)
+{
+	if (!vmc)
+		return -EINVAL;
+
+	list_del_init (&vmc->head);
+	vma_cache_free (vmc);
+	return 0;
+}
+
+static __inline__ struct vma_cache_struct *vma_cache_append (struct mm_struct *mm, struct vma_cache_struct *vmc, unsigned long addr, int len)
+{
+	struct vma_cache_struct *new;
+
+	new = vma_cache_alloc ();
+	if (!new)
+		return NULL;
+
+	INIT_LIST_HEAD (&new->head);
+	new->vm_start = addr;
+	new->vm_end   = addr+len;
+	list_add (&new->head, &vmc->head);
+	
+	return new;
+}
+
+static __inline__ struct vma_cache_struct *vma_cache_insert (struct mm_struct *mm, struct vma_cache_struct *vmc, unsigned long addr, int len)
+{
+	struct vma_cache_struct *new;
+
+	new = vma_cache_alloc ();
+	if (!new)
+		return NULL;
+
+	INIT_LIST_HEAD (&new->head);
+	new->vm_start = addr;
+	new->vm_end   = addr+len;
+	list_add_tail (&new->head, &vmc->head);
+	
+	return new;
+}
+
+void vma_cache_shtdn (struct mm_struct *mm)
+{
+	struct vma_cache_struct *nptr, *vmc, *head;
+	
+	head = list_entry (&mm->vma_cache_head, struct vma_cache_struct, head);
+	vmc  = head;
+	nptr = NULL;
+
+	while (nptr != head) {
+		nptr = next_area (vmc);
+		if (vma_cache_attach (mm, vmc->vm_start, vmc->vm_end-vmc->vm_start) == 0)
+			vma_cache_free (vmc);
+		vmc = nptr;
+	}
+}
+
+int vma_cache_clone (struct mm_struct *mm_dst, struct mm_struct *mm_src)
+{
+	struct list_head *tmp, *prev;
+	struct vma_cache_struct *new;
+
+	if (!list_empty (&mm_dst->vma_cache_head)) {
+		/* Remove previous mapping */
+	again:
+		list_for_each (tmp, &mm_dst->vma_cache_head) {
+			struct vma_cache_struct *vmc = list_entry (tmp, struct vma_cache_struct, head);
+			vma_cache_free (vmc);
+			goto again;
+		}
+		INIT_LIST_HEAD (&mm_dst->vma_cache_head);
+	}
+		
+	prev = &mm_dst->vma_cache_head;
+	list_for_each (tmp, &mm_src->vma_cache_head) {
+		struct vma_cache_struct *vmc = list_entry (tmp, struct vma_cache_struct, head);
+
+		new =  vma_cache_alloc ();
+		if (!new)
+			return -ENOMEM;
+		
+		INIT_LIST_HEAD (&new->head);
+		new->vm_start = vmc->vm_start;
+		new->vm_end   = vmc->vm_end;
+		list_add (&new->head, prev);
+		prev = &new->head;
+	}
+
+	return 0;
+}
+
+int vma_cache_init (struct mm_struct *mm)
+{
+	struct vma_cache_struct *vmc;
+	
+        INIT_LIST_HEAD (&mm->vma_cache_head);
+
+	vmc =  vma_cache_alloc ();
+	if (!vmc)
+		return -ENOMEM;
+
+	INIT_LIST_HEAD (&vmc->head);
+	vmc->vm_start = TASK_UNMAPPED_BASE;
+	vmc->vm_end   = TASK_SIZE;
+	list_add (&vmc->head, &mm->vma_cache_head);
+
+	return 0;
+}
+
+struct vma_cache_struct *vma_cache_find (struct mm_struct *mm, unsigned long addr, int len)
+{
+	struct list_head *tmp;
+
+	if (!len)
+		return NULL;
+
+	list_for_each (tmp, &mm->vma_cache_head) {
+		struct vma_cache_struct *vmc = list_entry (tmp, struct vma_cache_struct, head);
+		if (unmapped_area (vmc, addr, len))
+			return vmc;
+	}
+
+	return NULL;
+}
+
+/* 
+ * Give an address, find the left cache element and merge if mergeable.
+ */
+static struct vma_cache_struct *vma_cache_merge_left (struct mm_struct *mm, struct vma_cache_struct *vmc, unsigned long addr, int len)
+{
+	struct vma_cache_struct *vmc_left = NULL;
+
+	if (!vmc) {
+		vmc = vma_cache_find (mm, addr, len);
+		if (!vmc) goto out;
+	}
+
+	vmc_left = prev_area (vmc);
+
+	if (!vmc_left)
+		goto out;
+
+	if (vmc_left == vmc)
+		goto out;
+
+	/* merge */
+	if (vmc->vm_start <= vmc_left->vm_end && vmc->vm_start >= vmc_left->vm_start){ 
+		vmc_left->vm_end = vmc->vm_end;
+		vma_cache_chainout (mm, vmc);
+	}
+
+out:
+	return vmc_left;
+}
+
+/* 
+ * Give an address, find the right cache element and merge if mergeable.
+ */
+static struct vma_cache_struct *vma_cache_merge_right (struct mm_struct *mm, struct vma_cache_struct *vmc, unsigned long addr, int len)
+{
+	struct vma_cache_struct *vmc_right = NULL;
+
+	if (!vmc) {
+		vmc = vma_cache_find (mm, addr, len);
+		if (!vmc) goto out;
+	}
+
+	vmc_right = next_area (vmc);
+
+	if (!vmc_right)
+		goto out;
+
+	if (vmc_right == vmc)
+		goto out;
+
+	/* merge */
+	if (vmc->vm_end >= vmc_right->vm_start && vmc->vm_end <= vmc_right->vm_end) {
+		vmc_right->vm_start = vmc->vm_start;
+		vma_cache_chainout (mm, vmc);
+	}
+out:
+	return vmc_right;
+}
+
+int vma_cache_merge (struct mm_struct *mm, struct vma_cache_struct *vmc, unsigned long addr, int len)
+{
+	int err=0;
+
+	if (!vmc || vma_cache_find (mm, addr, len) == vmc) {
+		err  = (int )vma_cache_merge_left (mm, vmc, addr, len);
+		err |= (int )vma_cache_merge_right (mm, vmc, addr, len);
+	}
+
+	return (err)? -EINVAL : 0;
+}
+
+/*
+ * Insert or increase an existing area. Returns 0 if successfull.
+ */
+int vma_cache_attach (struct mm_struct *mm, unsigned long addr, int len)
+{
+	struct list_head *tmp;
+	struct vma_cache_struct *vmc;
+
+	if (!vma_cache_isvalid (mm, addr, len))
+		return -EINVAL;
+
+	vmc = list_entry (&mm->vma_cache_head, struct vma_cache_struct, head);
+	list_for_each (tmp, &mm->vma_cache_head) {
+		vmc = list_entry (tmp, struct vma_cache_struct, head);
+		
+		if (addr > vmc->vm_end)
+			continue;
+
+		if (pmapped_left (vmc, addr, len)) { 
+			vmc->vm_start = addr;
+			return vma_cache_merge (mm, vmc, addr, len);
+		}
+
+		if (unmapped_left (vmc, addr, len)) {
+			struct vma_cache_struct *new = vma_cache_insert (mm, vmc, addr, len);
+			if (!new)
+				return -ENOMEM;
+			return vma_cache_merge (mm, new, addr, len);
+		}
+		
+		if (pmapped_right (vmc, addr, len)) {
+			vmc->vm_end = addr+len;
+			return vma_cache_merge (mm, vmc, addr, len);
+		}
+
+		if (unmapped_area (vmc, addr, len))
+			return 0;
+
+		if (addr < vmc->vm_start && addr+len > vmc->vm_end) {
+			vmc->vm_start = addr;
+			vmc->vm_end   = addr+len;
+			return vma_cache_merge (mm, vmc, addr, len);
+		}
+
+		if (addr == vmc->vm_start && addr+len > vmc->vm_end) {
+			vmc->vm_end = addr+len;
+			return vma_cache_merge (mm, vmc, addr, len);
+		}
+	
+		/* shouldn't go here */
+		printk ("vma_cache_area: task '%s' [%d]. Don't know how to attach address range [%lx, %lx] in range [%lx, %lx]\n", 
+		      current->comm, current->pid, addr, addr+len, vmc->vm_start, vmc->vm_end);
+
+		break;
+	}
+
+	return -EINVAL;
+}
+
+/*
+ * Reserve a range of addresses. An error value is returned only if it's not
+ * possible to reserve this area.
+ */
+unsigned long vma_cache_area (struct mm_struct *mm, unsigned long addr, int len)
+{
+	struct vma_cache_struct *vmc;
+
+	if (!vma_cache_isvalid (mm, addr, len))
+		return addr;
+
+	vmc = vma_cache_find (mm, addr, len);
+	if (!vmc)
+		return addr;
+
+	if (addr == vmc->vm_start && addr+len <= vmc->vm_end) {
+		vmc->vm_start = addr+len;
+		if (vmc->vm_start == vmc->vm_end)
+			vma_cache_chainout (mm, vmc);
+		return addr;
+	}
+	
+	if (addr > vmc->vm_start && addr+len == vmc->vm_end) {
+		vmc->vm_end = addr;
+		if (vmc->vm_start == vmc->vm_end)
+			vma_cache_chainout (mm, vmc);
+		return addr;
+	}
+	
+	if (addr > vmc->vm_start && addr+len < vmc->vm_end) {
+		unsigned long old_end;
+
+		/* vmc->vm_start -> addr */
+		old_end = vmc->vm_end;
+		vmc->vm_end = addr;
+
+		/* addr+len -> vmc->vm_end */
+		vma_cache_append (mm, vmc, addr+len, old_end-addr-len);
+		return addr;
+	}
+
+	printk ("vma_cache_area: task '%s' [%d]. Don't know how to cache out address range [%lx, %lx] from range [%lx, %lx]\n", 
+		current->comm, current->pid, addr, addr+len, vmc->vm_start, vmc->vm_end);
+
+	return -EINVAL;
+}
+
+/* 
+ * Find the first available range of addresses. The return value
+ * is to satisfy get_unmapped_area().
+ */
+unsigned long vma_cache_detach (struct mm_struct *mm, int len)
+{
+	struct list_head *tmp;
+	unsigned long addr;
+
+	if (!len)
+		return -EINVAL;
+
+	addr = -ENOMEM;
+
+	list_for_each (tmp, &mm->vma_cache_head) {
+		struct vma_cache_struct *vmc = list_entry (tmp, struct vma_cache_struct, head);
+		
+		if (len <= vmc->vm_end - vmc->vm_start) {
+			addr = vmc->vm_start;
+			vmc->vm_start += len;
+			if (vmc->vm_start == vmc->vm_end)
+				vma_cache_chainout (mm, vmc);
+			break;
+		}
+	}
+	
+	return addr;
+}