Fix for for memory leak in IA32 mmap

David-

Here is a patch against linux-2.4.17-ia64-011226.diff' that fixes a memory leak with the IA32 mmap'/munmap' calls. The problem occurs when a non-fixed mmap' allocates a range that ends in the middle of a page. To handle problems with fixed requests the munmap' call rounds down the the area freed, causing the memory leak. The only solution I can think of to deal with this is to create a list of the allocated starting addresses for all non-fixed mmap' requests. `munmap' then checks this list and, if it finds a match, rounds the request size up rather than down.

I've tried the patch and it appears pretty reliable for me, I've run competing IA32 processes overnight with no problem and OpenOffice runs fine.

Don Dugger
"Censeo Toto nos in Kansa esse decisse." - D. Gale
[email protected]
Ph: 303/449-0877

diff -Naur linux-2.4.17-orig/arch/ia64/ia32/sys_ia32.c linux-2.4.17/arch/ia64/ia32/sys_ia32.c
@@ -324,14 +324,72 @@
 	return ret;
 }
 
+static void
+ia32_set_range(struct mmap_range *rp, unsigned int start)
+{
+	struct mmap_range *rg;
+
+	if ((rg = kmalloc(sizeof(*rg), GFP_KERNEL)) == (struct mmap_range *)0)
+		return;
+	rg->base = start;
+	rg->next = rp->next;
+	rp->next = rg;
+	return;
+}
+
+static int
+ia32_in_range(struct mmap_range *rp, unsigned int start)
+{
+	struct mmap_range *rg;
+
+	while ((rg = rp->next))
+		if (rg->base == start) {
+			rp->next = rg->next;
+			kfree(rg);
+			return(1);
+		} else
+			rp = rg;
+	return(0);
+}
+
+void
+ia32_delete_range(struct mmap_range *rp)
+{
+	struct mmap_range *rg;
+
+	while ((rg = rp)) {
+		rp = rp->next;
+		kfree(rg);
+	}
+	return;
+}
+
+void
+ia32_copy_range(struct mmap_range *rp)
+{
+	struct mmap_range *rg, *cg;
+
+	rp->next = (struct mmap_range *)0;
+	cg = (struct mmap_range *)&current->thread.mmap_range;
+	while ((cg = cg->next)) {
+		if ((rg = kmalloc(sizeof(*rg), GFP_KERNEL)) == (struct mmap_range *)0)
+			return;
+		rg->base = cg->base;
+		rg->next = rp->next;
+		rp->next = rg;
+	}
+	return;
+}
+
 static unsigned long
 emulate_mmap (struct file *file, unsigned long start, unsigned long len, int prot, int flags,
 	      loff_t off)
 {
-	unsigned long tmp, end, pend, pstart, ret, is_congruent, fudge = 0;
+	unsigned long tmp, end, orig, pend, pstart, ret, is_congruent, fudge = 0;
 	struct inode *inode;
 	loff_t poff;
 
+	orig = start;
 	end = start + len;
 	pstart = PAGE_START(start);
 	pend = PAGE_ALIGN(end);

@@ -415,6 +473,8 @@
 		if (!(prot & PROT_WRITE) && sys_mprotect(pstart, pend - pstart, prot) < 0)
 			return EINVAL;
 	}
+	if (orig == 0)
+		ia32_set_range((struct mmap_range *)&current->thread.mmap_range, (unsigned int)start);
 	return start;
 }
 

@@ -550,8 +610,11 @@
 	if (start > end)
 		return -EINVAL;
 
+	if (ia32_in_range((struct mmap_range *)&current->thread.mmap_range, start))
+		end = PAGE_ALIGN(end);
+	else
+		end = PAGE_START(end);
 	start = PAGE_ALIGN(start);
-	end = PAGE_START(end);
 
 	if (start >= end)
 		return 0;

diff -Naur linux-2.4.17-orig/arch/ia64/kernel/process.c linux-2.4.17/arch/ia64/kernel/process.c
@@ -308,8 +308,13 @@
 	 * If we're cloning an IA32 task then save the IA32 extra
 	 * state from the current task to the new task
 	 */
-	if (IS_IA32_PROCESS(ia64_task_regs(current)))
+	if (IS_IA32_PROCESS(ia64_task_regs(current))) {
 		ia32_save_state(p);
+		/*
+		 * Copy mmap ranges that might be needed for munmap calls
+		 */
+		ia32_copy_range((struct mmap_range *)&p->thread.mmap_range);
+	}
 #endif
 #ifdef CONFIG_PERFMON
 	if (p->thread.pfm_context)

@@ -516,6 +521,10 @@
 		 */
 		current->thread.flags &= ~IA64_THREAD_PM_VALID;
 	}
+#endif
+#ifdef CONFIG_IA32_SUPPORT
+	if (IS_IA32_PROCESS(ia64_task_regs(current)))
+		ia32_delete_range(current->thread.mmap_range);
 #endif
 }
 

diff -Naur linux-2.4.17-orig/include/asm-ia64/processor.h linux-2.4.17/include/asm-ia64/processor.h
@@ -348,6 +348,14 @@
 
 struct siginfo;
 
+struct mmap_range {
+	struct mmap_range	*next;
+	unsigned int		base;
+};
+
+void ia32_copy_range(struct mmap_range *);
+void ia32_delet_range(struct mmap_range *);
+
 struct thread_struct {
 	__u64 ksp;			/* kernel stack pointer */
 	unsigned long flags;		/* various flags */

@@ -365,7 +373,8 @@
 	__u64 ssd;			/* IA32 stack selector descriptor */
 	__u64 old_k1;			/* old value of ar.k1 */
 	__u64 old_iob;			/* old IOBase value */
-# define INIT_THREAD_IA32	0, 0, 0x17800000037fULL, 0, 0, 0, 0, 0, 0,
+	struct mmap_range *mmap_range;	/* mmap ranges */
+# define INIT_THREAD_IA32	0, 0, 0x17800000037fULL, 0, 0, 0, 0, 0, 0, 0,
 #else
 # define INIT_THREAD_IA32
 #endif /* CONFIG_IA32_SUPPORT */

Don> David- Here is a patch against linux-2.4.17-ia64-011226.diff' Don> that fixes a memory leak with the IA32 mmap'/munmap' calls. Don> The problem occurs when a non-fixed mmap' allocates a range Don> that ends in the middle of a page.

Nasty. You're talking about a _virtual_ address space leak, right? Do you know the exact sequence of events that causes application failure?

Don> To handle problems with
Don> fixed requests the `munmap' call rounds down the the area Don> freed, causing the memory leak. The only solution I can think Don> of to deal with this is to create a list of the allocated Don> starting addresses for all non-fixed mmap' requests. munmap' Don> then checks this list and, if it finds a match, rounds the Don> request size up rather than down.

It seems to me what we really want to do is keep track of partially mapped pages. I think we'd need a bitmask showing which ia32 pages have been mapped in an ia64 page. Say, a 16KB page whose first 4KB have been mapped would be represented as:

	       ia32 page:
	0	1	2	3

	1	0	0	0

now, if someone maps the 3rd 4KB page, you'd get:

	       ia32 page:
	0	1	2	3

	1	0	1	0

and so on. The underlying ia64 page would then have to be freed whenever the bitmask becomes empty.

	--david

David-

Yep, it was a virtual memory leak. Intel came up with a Fortran program that was allocating and freeing lots of anonymous mmap's. It was really nasty because it wasn't even the same request all the time, it had something like 3 different odd size requests that it was mmap'ing and `munmap'ing, all in a loop and eventually it ran out of VM.

I like the idea of keeping a bitmap. I still have to keep a list, it'll actually be a bigger list since I'll have to keep track of fixed requests also, but that should handle ALL cases (even the case where a program makes an odd sized non-fixed mmap' followed by a fixed mmap' into the middle of the last page). Give me a few days and I'll see if I can't come up with something.

Don Dugger
"Censeo Toto nos in Kansa esse decisse." - D. Gale
[email protected]
Ph: 303/449-0877

Don> David- Yep, it was a virtual memory leak. Intel came up with a Don> Fortran program that was allocating and freeing lots of Don> anonymous mmap's. It was really nasty because it wasn't even Don> the same request all the time, it had something like 3 Don> different odd size requests that it was mmap'ing and Don> `munmap'ing, all in a loop and eventually it ran out of VM.

OK, thanks for the background.

Don> I like the idea of keeping a bitmap. I still have to keep a Don> list, it'll actually be a bigger list since I'll have to keep Don> track of fixed requests also, but that should handle ALL cases Don> (even the case where a program makes an odd sized non-fixed Don> mmap' followed by a fixed mmap' into the middle of the last Don> page). Give me a few days and I'll see if I can't come up with Don> something.

Yes, I agree: the list is still needed and an entry needs to be created whenever an ia64 page is partially mapped.

Thanks,

	--david

I'm not sure that you really need a list ... in fact if you have a list, I think that I can still come up with pathalogical programs that will break: E.g. I might use several mmap() calls to set up some blocks of memory, but clear them all with one call to munmap() that spans them all, or I might not do any munmap() at all and just mmap(MAP_FIXED) things onto the same addresses (since mmap will throw away existing mappings before creating new ones). Just using the bitmap to determine whether to round up the end (and round down the start) address of munmap() requests based on whether the partial pages have been used should solve most of the problems.

IA-32 programs are limited to the bottom 4G of address space, and they believe that it is divided into 2^20 * 4KB pages. A bitmap for the whole of that would be 128KB, which might be somewhat high of an overhead for every IA-32 program ... but a two-level table would most likely be very sparsely filled, limiting the memory overhead to something acceptable.

Even with this change, there will still be programs that can only work correctly with a 4k kernel pagesize (e.g. a program that maps a 4K page from two different files, read+write into the same 16K page)

-Tony

P.S. Here is a C program that performs the same mmap/munmap operations in the same order as our nasty Fortran program:

#include <sys/mman.h>

main()

{
        void *a, *b, *c;
        int i;


        for (i = 0; i < 1000; i++) {
                a = mmap(0, 0x201000, PROT_READ|PROT_WRITE,
                        MAP_SHARED|MAP_ANONYMOUS, -1, 0);
                b = mmap(0, 0x101000, PROT_READ|PROT_WRITE, 
                        MAP_SHARED|MAP_ANONYMOUS, -1, 0);
                c = mmap(0, 0x101000, PROT_READ|PROT_WRITE, 
                        MAP_SHARED|MAP_ANONYMOUS, -1, 0);
                if ((long)a = -1 || (long)b = -1 || (long)c = -1)
                        abort();

                munmap(a, 0x201000);
                munmap(b, 0x101000);
                munmap(c, 0x101000);
        }

        return 0;
}

-----Original Message-----
From: David Mosberger [mailto:[email protected]]
Sent: Tuesday, March 05, 2002 10:59 AM
To: Don Dugger
Cc: [email protected]; [email protected]
Subject: Re: [Linux-ia64] Fix for for memory leak in IA32 mmap

Don> David- Yep, it was a virtual memory leak. Intel came up with a Don> Fortran program that was allocating and freeing lots of Don> anonymous mmap's. It was really nasty because it wasn't even Don> the same request all the time, it had something like 3 Don> different odd size requests that it was mmap'ing and Don> `munmap'ing, all in a loop and eventually it ran out of VM.

OK, thanks for the background.

Don> I like the idea of keeping a bitmap. I still have to keep a Don> list, it'll actually be a bigger list since I'll have to keep Don> track of fixed requests also, but that should handle ALL cases Don> (even the case where a program makes an odd sized non-fixed Don> mmap' followed by a fixed mmap' into the middle of the last Don> page). Give me a few days and I'll see if I can't come up with Don> something.

Yes, I agree: the list is still needed and an entry needs to be created whenever an ia64 page is partially mapped.

Thanks,

	--david

_______________________________________________
Linux-IA64 mailing list
[email protected]
http://lists.linuxia64.org/lists/listinfo/linux-ia64

Tony-

A couple of points:

1) Multiple mmap's all freed with 1 munmap'. If those were all non-fixed mmap's then that is a pretty broken program that deserves to fail (there is no guarantee that the mmap's returned contiguous memory). If they were all fixed `mmap's then there shouldn't be a problem even with the current scheme.

2) An mmap(MAP_FIXED) doesn't create a problem even now, it won't in the future.

3) I wasn't intending to keep a bitmap for all of IA32 addressable memory. I intend to keep a list of all the partial pages, basically the first and last page of an mmap' request, and then keep a bitmap for each of the 4K chunks inside of that page. Maintaining the bitmap will be a little tricky to handle all of the mmap/munmap' possibilities but it shouldn't be all that hard to get it right.

I agree, there could be a pathological IA32 program that just won't work without 4K pages, we've said all along that that is a possibility. Fortunately, we haven't found any real world programs that we can't make work yet and I'm going to try real hard to make sure that all real world programs work.

Don Dugger
"Censeo Toto nos in Kansa esse decisse." - D. Gale
[email protected]
Ph: 303/652-0870x117

Tony> I'm not sure that you really need a list ... in fact if you Tony> have a list, I think that I can still come up with Tony> pathalogical programs that will break: E.g. I might use Tony> several mmap() calls to set up some blocks of memory, but Tony> clear them all with one call to munmap() that spans them all, Tony> or I might not do any munmap() at all and just mmap(MAP_FIXED) Tony> things onto the same addresses (since mmap will throw away Tony> existing mappings before creating new ones). Just using the Tony> bitmap to determine whether to round up the end (and round Tony> down the start) address of munmap() requests based on whether Tony> the partial pages have been used should solve most of the Tony> problems.

That clearly would be wrong. I think Don was planning to handle the other cases you're mentioning as well.

Tony> IA-32 programs are limited to the bottom 4G of address space, Tony> and they believe that it is divided into 2^20 * 4KB pages. A Tony> bitmap for the whole of that would be 128KB, which might be Tony> somewhat high of an overhead for every IA-32 program ... but a Tony> two-level table would most likely be very sparsely filled, Tony> limiting the memory overhead to something acceptable.

Sounds like an interesting idea.

Tony> Even with this change, there will still be programs that can Tony> only work correctly with a 4k kernel pagesize (e.g. a program Tony> that maps a 4K page from two different files, read+write into Tony> the same 16K page)

Certainly. Anyone interested in exploring subpage support? This could also be useful for I/O devices... I am somewhat doubtful that the benefits would outweight the costs, but with some clever ideas, perhaps it would be possible to make it work for the important cases without incurring the full cost.

	--david

Aha! A list of the partial pages makes sense. I thought that the "list" was going to be a list of mmap'd ranges ... which would be tougher to get right in the face of pathalogical programs. I agree that these pathalogical programs deserve to fail, but they shouldn't take out the system (or tie it up with incredibly long lists of objects).

You might keep an eye on the complexity of the code for maintaining the lists
versus just having a (2-level) bitmap for the whole of the IA-32 address space. There are some tricky cases (especially when you factor in support for 64K kernel page size as well as 16K ... so your partial page bitmaps have different lengths for different configurations).

-Tony

Tony-

I'll keep the idea of a 2-level bitmap in mind but I don't see a problem with just a bitmap for partial pages. With a 64-bit long for the bitmap I can deal with page sizes up to 256K which should be sufficient. Since the page size is a compile time constant I just have to come up with suitable define macros and it should be relatively easy to deal with the bitmap.

Don Dugger
"Censeo Toto nos in Kansa esse decisse." - D. Gale
[email protected]
Ph: 303/652-0870x117