Skip to contentSkip to conversation

/proc/<n>/maps growing...

DISCUSSION David Luyer 8 participants 27 messages Aug 6, 2001 – Sep 3, 2001

Subsystems (15)
lore
Share & tools
lore
#0 lore raw

This is from evolution-mail.

It _looks_ like lots of contiguous, equal protection mappings which should be
merged:

40f00000-40f08000 rw-p 000bf000 00:00 0
40f08000-40f0e000 rw-p 000c7000 00:00 0
[... 37 lines deleted ...]
40f5e000-40f60000 rw-p 0011d000 00:00 0
40f60000-40f63000 rw-p 0011f000 00:00 0
40f63000-40f64000 rw-p 00000000 00:00 0
40f64000-40f65000 rw-p 00001000 00:00 0
[... 26 lines deleted ...]
40f88000-40f89000 rw-p 00025000 00:00 0
40f89000-40f8a000 rw-p 00026000 00:00 0
40f8a000-40f8b000 rw-p 00149000 00:00 0
40f8b000-40f8c000 rw-p 0014a000 00:00 0
[... 99 lines deleted ...]
40ff7000-40ff8000 rw-p 001b6000 00:00 0
40ff8000-40ff9000 rw-p 001b7000 00:00 0
40ff9000-40ffa000 rw-p 001b8000 00:00 0
40ffa000-41000000 ---p 001b9000 00:00 0
41000000-41026000 r--s 00000000 00:03 110985227 /SYSV00000000 (deleted) 41026000-41044000 r--s 00000000 00:03 111018010 /SYSV00000000 (deleted) 41100000-41101000 rw-p 000bc000 00:00 0
41101000-41102000 rw-p 00000000 00:00 0
41102000-41103000 rw-p 00001000 00:00 0
41103000-41104000 rw-p 00002000 00:00 0
41104000-41105000 rw-p 00003000 00:00 0
41105000-41108000 ---p 00004000 00:00 0
41108000-41200000 ---p 000c4000 00:00 0

and then a bit later:

[... much deleted ...]
40ff7000-40ff8000 rw-p 001b6000 00:00 0
40ff8000-40ff9000 rw-p 001b7000 00:00 0
40ff9000-40ffa000 rw-p 00000000 00:00 0
40ffa000-40ffc000 rw-p 00001000 00:00 0
40ffc000-40ffd000 rw-p 00000000 00:00 0
40ffd000-40ffe000 rw-p 001bc000 00:00 0
40ffe000-40fff000 rw-p 001bd000 00:00 0
40fff000-41000000 rw-p 001be000 00:00 0
41000000-41026000 r--s 00000000 00:03 110985227 /SYSV00000000 (deleted) 41026000-41044000 r--s 00000000 00:03 111018010 /SYSV00000000 (deleted) 41100000-41101000 rw-p 000bc000 00:00 0
41101000-41102000 rw-p 00000000 00:00 0
41102000-41103000 rw-p 00001000 00:00 0
41103000-41104000 rw-p 00002000 00:00 0
41104000-41105000 rw-p 00003000 00:00 0
41105000-41106000 rw-p 00004000 00:00 0
41106000-41107000 rw-p 00005000 00:00 0
41107000-41108000 rw-p 00006000 00:00 0
41108000-41109000 rw-p 000c4000 00:00 0
41109000-4110a000 rw-p 000c5000 00:00 0
4110a000-4110c000 rw-p 000c6000 00:00 0
4110c000-4110d000 rw-p 000c8000 00:00 0
4110d000-4110e000 rw-p 000c9000 00:00 0
4110e000-4110f000 rw-p 000ca000 00:00 0
4110f000-41110000 rw-p 000cb000 00:00 0
41110000-41112000 rw-p 000cc000 00:00 0
41112000-41113000 rw-p 000ce000 00:00 0
41113000-41115000 rw-p 000cf000 00:00 0
41115000-41200000 ---p 000d1000 00:00 0

So the maps are slowly splitting up even though the permissions are the same.

It seems to keep growing over time but Evolution isn't 100% stable yet so it
crashes for no apparent reason every 6 hours or so.. unless that could be when
it hits some 'limit' on the number of mappings allowed?

Signature · 4 lines
David Luyer                                     Phone:   +61 3 9674 7525
Engineering Projects Manager   P A C I F I C    Fax:     +61 3 9699 8693
Pacific Internet (Australia)  I N T E R N E T   Mobile:  +61 4 1111 2983
http://www.pacific.net.au/                      NASDAQ:  PCNTF
#1 lore raw

On Mon, Aug 06, 2001 at 04:41:21PM +1000, David Luyer wrote:

This is from evolution-mail.

What is it written in?

What libraries do it use?

Can you email me examples of the 'maps' files please? (off the list)

--cw

#2 lore raw
In reply to David Luyer
Quoted 3 lines · David Luyer

crashes for no apparent reason every 6 hours or so.. unless that could be when
it hits some 'limit' on the number of mappings allowed?

there's no limit, this is _only_ a performance issue, functionality is not compromised in any way [except possibly wasting some memory resources that could lead to running out of memory earlier].

I personally like the clever merging to happen in the kernel at the latest possible layer, like we do for blkdev in respect to the fs and skbs with respect to the senders (as opposed to the scatter-gather based apis where the user has to merge always in userspace to avoid wasting metadata space).

But my strongest argument is probably that unless I'm missing something the merge_segments could be implemented with zero cost (with a cost of the order of a few cycles per mmap call, not with a full lookup of the avl which is actually why Linus doesn't like it). This because as far as we were able to insert the new vma into the data structure in the right place, we also known something about the 'prev' vma at some point during insert_vma_struct, so we only need to get such a pointer out of insert_vm_struct at nearly zero cost, instead of running find_vma_prev again inside merge_segments and browse the whole tree for a second time. Can somebody see a problem with this design?

In short I believe if we implement it right it is an obvious and worthwhile optimization (however I certainly can see that in 2.[23] the double vma lookup at every mmap wasn't very nice).

I guess I will implement the above proposal it if nobody else is interested to do that (and while implementing it I will certainly notice if I was missing something or not :).

Andrea

#3 lore raw
Quoted 1 line · Andrea Arcangeli

Can somebody see a problem with this design?

As someone who was involved when the merge_segments stuff got tossed by Linus, the reason was that the locking is utterly atrocious.

After trying to get the SMP locking correct _four_ times, Linus basically said to me "This merging so stupidly complex, and we don't need it at all. We only need merging for very simple cases."

I think he's right. The old code was trying to do everything and made the locking more difficult than it needed to be.

Later,
David S. Miller
[email protected]

#4 lore raw
Quoted 5 lines · David S. Miller
Quoted 1 line · Andrea Arcangeli

Can somebody see a problem with this design?

As someone who was involved when the merge_segments stuff got tossed by Linus, the reason was that the locking is utterly atrocious.

Mmmm, don't we ONLY need to hold both the mm->mmap_sem for write access and the mm->page_table_lock ?

... which we are already holding at that point.

regards,

Rik
--
Executive summary of a recent Microsoft press release:
"we are concerned about the GNU General Public License (GPL)"

		http://www.surriel.com/

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

#5 lore raw
Quoted 9 lines · Rik van Riel
Quoted 5 lines · David S. Miller
Quoted 1 line · Andrea Arcangeli

Can somebody see a problem with this design?

As someone who was involved when the merge_segments stuff got tossed by Linus, the reason was that the locking is utterly atrocious.

Mmmm, don't we ONLY need to hold both the mm->mmap_sem for write access and the mm->page_table_lock ?

No. We used to merge non-NULL files too in 2.2.x, which meant that we had to also hold mapping->i_shared_lock.

Also, the locking order for that is (due to the MM layer) _different_ from the one we'd like: we need to get the "i_shared_lock" before we get the page table lock.

ALSO, we have the issue of calling the "vm_ops->open()" routine - we need to call that one with the MM semaphore held, but without any of the spinlocks held. This one is also kind of interesting: if we merge with an existing memory map we must _not_ call the open routine at all (it's already open), while if we add a new one we do have to call it.

This was another reason why I removed the merging: I could not for the life of me see how that merging could possibly be correct with some of the special character drivers we have right now. In particular, some drivers "open()" routines not just increment usage counts, but also check the limits and allocate backing space.

Which means that there is _no_ way we can merge such a vma - we'd have to call "->open()" for it to get the security checks etc, but we could not increment usage counts, or whatever.

So what the old merging code used to do was:
- ignore the fundamental "->open()" problem, on the theory that it doesn't happen in real life (correct, btw. But it can happen if you're a cracker trying to break in to the system)
- get and drop the locks, which meant that we did hold the locks for all the operations we did, but we dropped them in between - so the code would drop the page table lock, get the i_shared_lock, and re-get the page table lock etc.

Did I mention that the old code was buggy and slow? And that fixing it was hard? Which is, surprise surprise, why 2.4.x takes the approach of merging only things that it _knows_ are (a) common and (b) safe to merge.

Linus

#6 lore raw
In reply to David Luyer

On Mon, Aug 06, 2001 at 02:20:42AM -0700, David S. Miller wrote:

I think he's right. The old code was trying to do everything and made the locking more difficult than it needed to be.

I just posted an analysis of this (a bit nebulous and hand-waving in nature) which seems to indicate to me this _can_ probably be fixed in userspace, specifically glibc.

Not not that I've checked the glibc code recently...

< .... wanders off to try to grok glibc .... >

--cw

#7 lore raw
In reply to David Luyer
Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · David Luyer

crashes for no apparent reason every 6 hours or so.. unless that could be when
it hits some 'limit' on the number of mappings allowed?

there's no limit, this is _only_ a performance issue, functionality is not compromised in any way [except possibly wasting some memory resources that could lead to running out of memory earlier].

There is a limit, /proc/sys/vm/max_map_count.
I believe this is what I reported a few weeks ago:
mprotect(2) does not ever attempt to merge segments, even for simple cases. glibc malloc, if it runs out of normal brk heap, always allocates a fixed size new heap (I think by default 2MB) aligned to its size and as the
memory is needed it always mprotects the area (e.g. page) which needs to be allocated, so that it is readable/writeable.
So, e.g. for program which calls malloc(1024) in a loop,
the sequence of syscalls that glibc does once it runs out of brk is basically:
mmap2(NULL, 2097152, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0) = 0x40300000
munmap(0x40400000, 1048576) = 0
mprotect(0x40300000, 32768, PROT_READ|PROT_WRITE) = 0
mprotect(0x40308000, 4096, PROT_READ|PROT_WRITE) = 0
mprotect(0x40309000, 4096, PROT_READ|PROT_WRITE) = 0
...

mprotect(0x403fd000, 4096, PROT_READ|PROT_WRITE) = 0
mprotect(0x403fe000, 4096, PROT_READ|PROT_WRITE) = 0
mprotect(0x403ff000, 4096, PROT_READ|PROT_WRITE) = 0

mmap2(NULL, 2097152, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0) = 0x40400000
munmap(0x40400000, 0) = -1 EINVAL (Invalid argument)
munmap(0x40500000, 1048576) = 0
mprotect(0x40400000, 32768, PROT_READ|PROT_WRITE) = 0
mprotect(0x40408000, 4096, PROT_READ|PROT_WRITE) = 0
...

mprotect(0x509fd000, 4096, PROT_READ|PROT_WRITE) = 0
mprotect(0x509fe000, 4096, PROT_READ|PROT_WRITE) = 0
mprotect(0x509ff000, 4096, PROT_READ|PROT_WRITE) = 0

Each of these mprotect calls creates a new vma (although just growing the prev would be sufficient).

This has the bad effect that one can (using malloc(1024)) allocate only a small fraction of the available virtual address space (e.g. on i386 something like 1.1GB, ie. far less than 2.8GB which can be allocated if /proc/sys/vm/max_map_count is bumped to say 512000).

Also, there is a bug in mprotect that it does not check max_map_count before insert_vm_struct unlike mmap.c and other places. So, such malloc(1024) loop allocates slightly more than max_map_count vma's until it gets hit in the mmap syscall. But it should not be hard to construct a program which would eat many times max_map_count (just mmap PROT_NONE most of VA, then mprotect page by page).

Jakub

#8 lore raw
In reply to David Luyer
Quoted 11 lines · Jakub Jelinek
Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · David Luyer

crashes for no apparent reason every 6 hours or so.. unless that could be when
it hits some 'limit' on the number of mappings allowed?

there's no limit, this is _only_ a performance issue, functionality is not compromised in any way [except possibly wasting some memory resources that could lead to running out of memory earlier].

There is a limit, /proc/sys/vm/max_map_count.

in mainline it's not a sysctl, btw.

I never noticed this limit and personally I don't like it regardless of the merge_segments (but of course without merge_segments it is can trigger problems while switching between 2.2 and 2.4).

Andrea

#9 lore raw
Quoted 6 lines · Andrea Arcangeli

in mainline it's not a sysctl, btw.

I never noticed this limit and personally I don't like it regardless of the merge_segments (but of course without merge_segments it is can trigger problems while switching between 2.2 and 2.4).

Whether you like it or not is immaterial.

It means that users cannot allocate tons of memory by mmap'ing every odd page, for example.

And yes, this used to be a way to lock up a machine. With a exploit that was floating on the net.

That limit is _needed_.

Linus

#10 lore raw
In reply to David Luyer
Quoted 7 lines · David S. Miller
Quoted 1 line · Andrea Arcangeli

Can somebody see a problem with this design?

As someone who was involved when the merge_segments stuff got tossed by Linus, the reason was that the locking is utterly atrocious.

Quoted 6 lines

After trying to get the SMP locking correct _four_ times, Linus basically said to me "This merging so stupidly complex, and we don't need it at all. We only need merging for very simple cases."

I think he's right. The old code was trying to do everything and made the locking more difficult than it needed to be.

The point here is not if it's simple or difficult. The point is what can be done or not and what is faster or slower. All I'm saying is that I don't see why it's not possible to implement the merge_segments with only an O(1) additional cost of a few cycles per mmap syscall, which will render the feature an obvious improvement (instead of being a dubious improvement like in 2.2 that is walking the tree two times).

If it was simple to implement it you would just find the patch attached to this email 8).

Andrea

#11 lore raw
In reply to David Luyer
Quoted 7 lines · Andrea Arcangeli
Quoted 6 lines · Jakub Jelinek
Quoted 5 lines · Andrea Arcangeli
Quoted 3 lines · David Luyer

crashes for no apparent reason every 6 hours or so.. unless that could be when
it hits some 'limit' on the number of mappings allowed?

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

there's no limit, this is _only_ a performance issue, functionality is not compromised in any way [except possibly wasting some memory resources that could lead to running out of memory earlier].

There is a limit, /proc/sys/vm/max_map_count.

in mainline it's not a sysctl, btw.

Even worse, it means people not using -ac kernels cannot malloc a lot of memory but by recompiling the kernel.

Jakub

#12 lore raw
Quoted 3 lines · Jakub Jelinek

Even worse, it means people not using -ac kernels cannot malloc a lot of memory but by recompiling the kernel.

Hey guys. Let's calm down a bit, and look at the problem.

Why the hell is glibc doing something so stupid in the first place? Yes, we can work around it, but it sounds like the glibc apporoach is slow and stupid even if we _did_ work around it. Mind explaining what the logic of "fixing" the kernel is?

Linus

#13 lore raw
Quoted 9 lines
Quoted 2 lines

Even worse, it means people not using -ac kernels cannot malloc a lot of memory but by recompiling the kernel.

Hey guys. Let's calm down a bit, and look at the problem.

Why the hell is glibc doing something so stupid in the first place? Yes, we can work around it, but it sounds like the glibc apporoach is slow and stupid even if we _did_ work around it. Mind explaining what the logic of "fixing" the kernel is?

Its two problems

1. mprotect not doing the right resource checks
2. mprotect not doing the simple merges

The resource one is a kernel problem. I am curious why only specific apps trip the second case

#14 lore raw
In reply to Linus Torvalds

On Mon, Aug 06, 2001 at 06:26:52PM +0100, Alan Cox wrote:

The resource one is a kernel problem. I am curious why only specific apps trip the second case

See my longish posting about about this, depending on the 'growth' of memory, glibc uses different allocation meachnisms, for allocationes between 8k and 1M, this pattern happens to really suck.

Different memory allocators behave differently, I tried to write a library to wrap malloc with libhoard but become horribly unstuck when dlsym wanted to start calling malloc (and I couldn't get ld --wrap to do what I wanted).

--cw

#15 lore raw
In reply to David Luyer
Quoted 3 lines · Andrea Arcangeli

I never noticed this limit and personally I don't like it regardless of the merge_segments (but of course without merge_segments it is can trigger problems while switching between 2.2 and 2.4).

Note that mprotect has this behaviour even if the mprotect range covers the area before it, so unless the heap is allocated without PROT_NONE initially with mprotect calls later, there isn't anything glibc can do to avoid this.

The program below creates 3 times 10 new vma areas:

#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>

int main(void)
{
void *p, *q, *r;
p = mmap(NULL, 10*4096, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0); printf ("p %p\n", p);

  mprotect(p+1*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+2*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+3*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+4*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+5*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+6*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+7*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(p+8*4096, 4096, PROT_READ|PROT_WRITE);
  q = mmap(NULL, 10*4096, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0);
  printf ("q %p\n", q);
  mprotect(q+1*4096, 4096, PROT_READ|PROT_WRITE);
  mprotect(q+1*4096, 8192, PROT_READ|PROT_WRITE);
  mprotect(q+2*4096, 8192, PROT_READ|PROT_WRITE);
  mprotect(q+3*4096, 8192, PROT_READ|PROT_WRITE);
  mprotect(q+4*4096, 8192, PROT_READ|PROT_WRITE);
  mprotect(q+5*4096, 8192, PROT_READ|PROT_WRITE);
  mprotect(q+6*4096, 8192, PROT_READ|PROT_WRITE);
  mprotect(q+7*4096, 8192, PROT_READ|PROT_WRITE);
  r = mmap(NULL, 10*4096, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0);
  printf ("r %p\n", r);
  mprotect(r+4096, 1*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 2*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 3*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 4*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 5*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 6*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 7*4096, PROT_READ|PROT_WRITE);
  mprotect(r+4096, 8*4096, PROT_READ|PROT_WRITE);

fflush(stdout);
pause();
return 0;
}

Jakub

#16 lore raw
In reply to David Luyer
Quoted 12 lines · Jakub Jelinek
Quoted 11 lines · Andrea Arcangeli
Quoted 10 lines · Jakub Jelinek
Quoted 8 lines · Andrea Arcangeli
Quoted 3 lines · David Luyer

crashes for no apparent reason every 6 hours or so.. unless that could be when
it hits some 'limit' on the number of mappings allowed?

there's no limit, this is _only_ a performance issue, functionality is not compromised in any way [except possibly wasting some memory resources that could lead to running out of memory earlier].

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

There is a limit, /proc/sys/vm/max_map_count.

in mainline it's not a sysctl, btw.

Even worse, it means people not using -ac kernels cannot malloc a lot of memory but by recompiling the kernel.

Not that I consider the -ac situation optimal either (however certainly it's better): if you don't have root privilegies you are screwed. And this is again not related to merge_segments, the same problem can arise with the merge_segments in place (but with merge_segments in place it would probably trigger legally only on 64bit boxes with some dozen gigabytes of ram). (this is why I didn't liked that limit ;)

The downside of dropping the limit is that we allow the user to allocate an unlimited amount of unswappable ram per-process (and the current oom killer will do the very wrong thing since it has no idea of the ram allocated in the vmas of the process). Nothing compared to cp /dev/zero /dev/shm though...

Andrea

#17 lore raw
In reply to David Luyer

On Mon, Aug 06, 2001 at 12:57:05PM +0200, Andrea Arcangeli wrote:

The point here is not if it's simple or difficult. The point is what can be done or not and what is faster or slower. All I'm saying is that I don't see why it's not possible to implement the merge_segments with only an O(1) additional cost of a few cycles per mmap syscall, which will render the feature an obvious improvement (instead of being a dubious improvement like in 2.2 that is walking the tree two times).

mmap does merge in many common cases.

--cw

#18 lore raw
In reply to David Luyer
Quoted 1 line · Chris Wedgwood

mmap does merge in many common cases.

(assuming you speak about 2.2 because 2.4 obviously doesn't merge anything and that's the point of the discussion) So what? What do you mean with your observation?

Andrea

#19 lore raw
Quoted 6 lines · Andrea Arcangeli
Quoted 1 line · Chris Wedgwood

mmap does merge in many common cases.

(assuming you speak about 2.2 because 2.4 obviously doesn't merge anything and that's the point of the discussion) So what? What do you mean with your observation?

2.4.x _does_ merge. Look for yourself. It doesn't merge mprotects, no. And why should glibc do mprotect() for a malloc() call? Electric Fence, yes. glibc, no.

Linus

#20 lore raw
Quoted 3 lines · Linus Torvalds

2.4.x _does_ merge. Look for yourself. It doesn't merge mprotects, no. And why should glibc do mprotect() for a malloc() call? Electric Fence, yes. glibc, no.

What glibc does (when it decided to allocate in this way) is:

mmap(NULL,2*sz,PROT_NONE,MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE,-1,0)

free up 1*sz of space which isn't sz-aligned (presumably to prevent fragmentation of its pools, now I think about it)

allocate out bits of the block mprotecting them as PROT_READ|PROT_WRITE as it goes

Typically it's releasing multiples of 4kb at a time just like it brk()s multiples of 4kb at a time. glibc doesn't catch accesses right down to the byte but does catch accesses which are 'way off'. But really, yes, you're right - if it's not catching everything it shouldn't catch anything, since it's not its job. Unless the MAP_NORESERVE with PROT_NONE is saving the system from even thinking about the unused parts of the large slab glibc has just grabbed, in which case there is some reason glibc should do things the way it does.

Signature · 4 lines
David Luyer                                     Phone:   +61 3 9674 7525
Engineering Projects Manager   P A C I F I C    Fax:     +61 3 9699 8693
Pacific Internet (Australia)  I N T E R N E T   Mobile:  +61 4 1111 2983
http://www.pacific.net.au/                      NASDAQ:  PCNTF
#21 lore raw
In reply to David Luyer

On Mon, Aug 06, 2001 at 02:36:03PM +0200, Andrea Arcangeli wrote:

(assuming you speak about 2.2 because 2.4 obviously doesn't merge anything and that's the point of the discussion) So what? What do you mean with your observation?

for anonymous maps, when it can extend the previos map, mmap will do so --- it happens to occur quite often in practice

--cw

#22 lore raw
In reply to David Luyer
Quoted 2 lines · Chris Wedgwood

for anonymous maps, when it can extend the previos map, mmap will do so --- it happens to occur quite often in practice

ah, what an horrible hack, so we just walk the tree _two_ times and we don't even take advantage of that (over)work as we should!

Andrea

#23 lore raw
Quoted 6 lines · Andrea Arcangeli
Quoted 2 lines · Chris Wedgwood

for anonymous maps, when it can extend the previos map, mmap will do so --- it happens to occur quite often in practice

ah, what an horrible hack, so we just walk the tree _two_ times and we don't even take advantage of that (over)work as we should!

I wouldn't classify it as a horrible hack... but.

It isn't doing the "other work" because:

1) The locking is really horrible. You have to drop/reget the VMA and mm locks if you want to link/unlink other vmas to do the merging.

2) For mmap() itself these other cases not being handled now happen so rarely.

So instead of an abortion like merge_segments() which tried to be everything to everybody, we have 4 lines of code.

The issue is mprotect() anyways. I bet we can add something which, while not as simple as the mmap() code, is not overly complex yet will make this glibc mprotect() case happy.

On the topic of mmap limits, it is really a job for something like Andrey Savochkin's bean counter patches.

Later,
David S. Miller
[email protected]

#24 lore raw
In reply to David Luyer
Quoted 1 line · David S. Miller

I wouldn't classify it as a horrible hack... but.

The part I find worse is that we just walk the tree two times.

I believe the best way is to allocate always the new vma, and to hide the merging into the lowlevel of a new insert_vm_struct (with a special function ala merge_segments that we can share with mprotect like in 2.2).

For example we could limit such special function to merge only the anonymous mappings if we don't want to solve the locking issues (the abortion), so it could remain simple but generic and optimized to avoid walking the tree, allocating and freeing a slab cache is O(1) operation when there's no memory pressore, much better than browsing a tree two times at every malloc with a two liner that avoids hitting the max_limit while we recall malloc. (of course for mremap we'll keep browsing the tree twice but we cannot avoid that)

Andrea

#25 lore raw
Quoted 5 lines · Andrea Arcangeli
Quoted 1 line · David S. Miller

I wouldn't classify it as a horrible hack... but.

The part I find worse is that we just walk the tree two times.

Try it without doing it - the code grows quite nasty without completely getting rid of "insert_vm_struct()".

Which I considered, but decided that 2.4.x is not the time to do so.

Quoted 3 lines

I believe the best way is to allocate always the new vma, and to hide the merging into the lowlevel of a new insert_vm_struct (with a special function ala merge_segments that we can share with mprotect like in 2.2).

Oh, and THAT is going to speed things up?

Hint: the merging actually happens at a fairly high percentage for the common cases. We win more by walking the tree twice and avoiding the unnecessary allocation/free.

Now, if you _really_ want to do this right, you can:
- hold the write lock on the semaphore. Nobody is going to change the list.

- walk the table just once, remembering what the previous entry was.

NOTE! You ahve to do this _anyway_, as part of checking the "do I need to unmap anything?" Right now we just call "do_munmap()", but done right we would walk the tree _once_, noticing whether we need to unmap or not, and keep track of what the previous one was.

- just expand the previous entry when you notice that it's doable.

- allocate and insert a new entry if needed.

However, this absolutely means getting rid of "insert_vm_struct()", and moving a large portion of it into the caller.

It also means doing the same for "do_munmap()".

Try it. I'd love to see the code. I didn't want to do it myself.

And remember: optimize for _well_written applications. Not for stupid glibc code that can be fixed.

Linus

#26 lore raw

mmap-rb-7 [was Re: /proc/<n>/maps growing...]

In reply to Andrea Arcangeli
Quoted 13 lines · Linus Torvalds

Now, if you _really_ want to do this right, you can:
- hold the write lock on the semaphore. Nobody is going to change the list.

- walk the table just once, remembering what the previous entry was.

NOTE! You ahve to do this _anyway_, as part of checking the "do I need to unmap anything?" Right now we just call "do_munmap()", but done right we would walk the tree _once_, noticing whether we need to unmap or not, and keep track of what the previous one was.

- just expand the previous entry when you notice that it's doable.

Quoted 8 lines

- allocate and insert a new entry if needed.

However, this absolutely means getting rid of "insert_vm_struct()", and moving a large portion of it into the caller.

It also means doing the same for "do_munmap()".

Try it. I'd love to see the code. I didn't want to do it myself.

It's below, now rock solid, please include in the next kernel.

A few implementation details: the do_munmap case inside mmap(2) it's not an extremely common case so I will walk the tree once more if there's an overlapping mapping under us. Also for the non MAP_FIXED mappings we'll still walk the tree twice in mmap(2) because I didn't messed with the get_unmapped_area API.

arch/alpha/kernel/process.c +0 -1
diff -urN 2.4.10pre4/arch/alpha/kernel/process.c mmap-rb/arch/alpha/kernel/process.c
@@ -50,7 +50,6 @@
  */
 
 unsigned long init_user_stack[1024] = { STACK_MAGIC, };
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/arm/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/arm/kernel/init_task.c mmap-rb/arch/arm/kernel/init_task.c
@@ -9,7 +9,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/cris/kernel/process.c +0 -1
diff -urN 2.4.10pre4/arch/cris/kernel/process.c mmap-rb/arch/cris/kernel/process.c
@@ -65,7 +65,6 @@
  * setup.
  */
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/i386/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/i386/kernel/init_task.c mmap-rb/arch/i386/kernel/init_task.c
@@ -6,7 +6,6 @@
 #include <asm/pgtable.h>
 #include <asm/desc.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/ia64/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/ia64/kernel/init_task.c mmap-rb/arch/ia64/kernel/init_task.c
@@ -13,7 +13,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/m68k/kernel/process.c +0 -1
diff -urN 2.4.10pre4/arch/m68k/kernel/process.c mmap-rb/arch/m68k/kernel/process.c
@@ -38,7 +38,6 @@
  * alignment requirements and potentially different initial
  * setup.
  */
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/mips/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/mips/kernel/init_task.c mmap-rb/arch/mips/kernel/init_task.c
@@ -4,7 +4,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/mips64/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/mips64/kernel/init_task.c mmap-rb/arch/mips64/kernel/init_task.c
@@ -4,7 +4,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/parisc/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/parisc/kernel/init_task.c mmap-rb/arch/parisc/kernel/init_task.c
@@ -6,7 +6,6 @@
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/ppc/kernel/process.c +0 -1
diff -urN 2.4.10pre4/arch/ppc/kernel/process.c mmap-rb/arch/ppc/kernel/process.c
@@ -48,7 +48,6 @@
 
 struct task_struct *last_task_used_math = NULL;
 struct task_struct *last_task_used_altivec = NULL;
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/s390/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/s390/kernel/init_task.c mmap-rb/arch/s390/kernel/init_task.c
@@ -12,7 +12,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/s390x/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/s390x/kernel/init_task.c mmap-rb/arch/s390x/kernel/init_task.c
@@ -12,7 +12,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/sh/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/sh/kernel/init_task.c mmap-rb/arch/sh/kernel/init_task.c
@@ -5,7 +5,6 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/sparc/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/sparc/kernel/init_task.c mmap-rb/arch/sparc/kernel/init_task.c
@@ -4,7 +4,6 @@
 #include <asm/pgtable.h>
 #include <asm/uaccess.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
arch/sparc64/kernel/init_task.c +0 -1
diff -urN 2.4.10pre4/arch/sparc64/kernel/init_task.c mmap-rb/arch/sparc64/kernel/init_task.c
@@ -4,7 +4,6 @@
 #include <asm/pgtable.h>
 #include <asm/uaccess.h>
 
-static struct vm_area_struct init_mmap = INIT_MMAP;
 static struct fs_struct init_fs = INIT_FS;
 static struct files_struct init_files = INIT_FILES;
 static struct signal_struct init_signals = INIT_SIGNALS;
include/asm-alpha/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-alpha/processor.h mmap-rb/include/asm-alpha/processor.h
@@ -70,9 +70,6 @@
 	int bpt_nsaved;
 };
 
-#define INIT_MMAP { &init_mm, PAGE_OFFSET,  PAGE_OFFSET+0x10000000, \
-	NULL, PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  { \
 	0, 0, 0, \
 	0, 0, 0, \
include/asm-arm/processor.h +0 -7
diff -urN 2.4.10pre4/include/asm-arm/processor.h mmap-rb/include/asm-arm/processor.h
@@ -68,13 +68,6 @@
 	EXTRA_THREAD_STRUCT
 };
 
-#define INIT_MMAP {					\
-	vm_mm:		&init_mm,			\
-	vm_page_prot:	PAGE_SHARED,			\
-	vm_flags:	VM_READ | VM_WRITE | VM_EXEC,	\
-	vm_avl_height:	1,				\
-}
-
 #define INIT_THREAD  {					\
 	refcount:	ATOMIC_INIT(1),			\
 	EXTRA_THREAD_STRUCT_INIT			\
include/asm-cris/processor.h +0 -10
diff -urN 2.4.10pre4/include/asm-cris/processor.h mmap-rb/include/asm-cris/processor.h
@@ -77,16 +77,6 @@
 
 #define current_regs() user_regs(current)
 
-/* INIT_MMAP is the kernels map of memory, between KSEG_C and KSEG_D */
-
-#ifdef CONFIG_CRIS_LOW_MAP
-#define INIT_MMAP { &init_mm, KSEG_6, KSEG_7, NULL, PAGE_SHARED, \
-			     VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-#else
-#define INIT_MMAP { &init_mm, KSEG_C, KSEG_D, NULL, PAGE_SHARED, \
-			     VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-#endif
-
 #define INIT_THREAD  { \
    0, 0, 0x20 }  /* ccr = int enable, nothing else */
 
include/asm-i386/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-i386/processor.h mmap-rb/include/asm-i386/processor.h
@@ -391,9 +391,6 @@
 	0,{~0,}			/* io permissions */		\
 }
 
-#define INIT_MMAP \
-{ &init_mm, 0, 0, NULL, PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_TSS  {						\
 	0,0, /* back_link, __blh */				\
 	sizeof(init_stack) + (long) &init_stack, /* esp0 */	\
include/asm-ia64/processor.h +0 -5
diff -urN 2.4.10pre4/include/asm-ia64/processor.h mmap-rb/include/asm-ia64/processor.h
@@ -364,11 +364,6 @@
 	struct ia64_fpreg fph[96];	/* saved/loaded on demand */
 };
 
-#define INIT_MMAP {								\
-	&init_mm, PAGE_OFFSET, PAGE_OFFSET + 0x10000000, NULL, PAGE_SHARED,	\
-        VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL				\
-}
-
 #define INIT_THREAD {					\
 	0,				/* ksp */	\
 	0,				/* flags */	\
include/asm-m68k/processor.h +0 -2
diff -urN 2.4.10pre4/include/asm-m68k/processor.h mmap-rb/include/asm-m68k/processor.h
@@ -78,8 +78,6 @@
 	unsigned char  fpstate[FPSTATESIZE];  /* floating point state */
 };
 
-#define INIT_MMAP { &init_mm, 0, 0x40000000, NULL, __pgprot(_PAGE_PRESENT|_PAGE_ACCESSED), VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  { \
 	sizeof(init_stack) + (unsigned long) init_stack, 0, \
 	PS_S, __KERNEL_DS, \
include/asm-mips/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-mips/processor.h mmap-rb/include/asm-mips/processor.h
@@ -171,9 +171,6 @@
 
 #endif /* !defined (_LANGUAGE_ASSEMBLY) */
 
-#define INIT_MMAP { &init_mm, KSEG0, KSEG1, NULL, PAGE_SHARED, \
-                    VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  { \
         /* \
          * saved main processor registers \
include/asm-mips64/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-mips64/processor.h mmap-rb/include/asm-mips64/processor.h
@@ -198,9 +198,6 @@
 
 #endif /* !defined (_LANGUAGE_ASSEMBLY) */
 
-#define INIT_MMAP { &init_mm, KSEG0, KSEG1, NULL, PAGE_SHARED, \
-                    VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  { \
         /* \
          * saved main processor registers \
include/asm-parisc/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-parisc/processor.h mmap-rb/include/asm-parisc/processor.h
@@ -107,9 +107,6 @@
 /* Thread struct flags. */
 #define PARISC_KERNEL_DEATH	(1UL << 31)	/* see die_if_kernel()... */
 
-#define INIT_MMAP { &init_mm, 0, 0, NULL, PAGE_SHARED, \
-		    VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD { {			\
 	{ 0, 0, 0, 0, 0, 0, 0, 0,	\
 	  0, 0, 0, 0, 0, 0, 0, 0,	\
include/asm-ppc/processor.h +0 -8
diff -urN 2.4.10pre4/include/asm-ppc/processor.h mmap-rb/include/asm-ppc/processor.h
@@ -621,14 +621,6 @@
 }
 
 /*
- * Note: the vm_start and vm_end fields here should *not*
- * be in kernel space.  (Could vm_end == vm_start perhaps?)
- */
-#define INIT_MMAP { &init_mm, 0, 0x1000, NULL, \
-		    PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, \
-		    1, NULL, NULL }
-
-/*
  * Return saved PC of a blocked thread. For now, this is the "user" PC
  */
 static inline unsigned long thread_saved_pc(struct thread_struct *t)
include/asm-s390/processor.h +0 -4
diff -urN 2.4.10pre4/include/asm-s390/processor.h mmap-rb/include/asm-s390/processor.h
@@ -95,10 +95,6 @@
 
 typedef struct thread_struct thread_struct;
 
-#define INIT_MMAP \
-{ &init_mm, 0, 0, NULL, PAGE_SHARED, \
-VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD { (struct pt_regs *) 0,                       \
                     { 0,{{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}, \
 			    {0},{0},{0},{0},{0},{0}}},            \
include/asm-s390x/processor.h +0 -4
diff -urN 2.4.10pre4/include/asm-s390x/processor.h mmap-rb/include/asm-s390x/processor.h
@@ -99,10 +99,6 @@
 
 typedef struct thread_struct thread_struct;
 
-#define INIT_MMAP \
-{ &init_mm, 0, 0, NULL, PAGE_SHARED, \
-VM_READ | VM_WRITE | VM_EXEC, 1, NULL,NULL }
-
 #define INIT_THREAD { (struct pt_regs *) 0,                       \
                     { 0,{{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}, \
 			    {0},{0},{0},{0},{0},{0}}},            \
include/asm-sh/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-sh/processor.h mmap-rb/include/asm-sh/processor.h
@@ -114,9 +114,6 @@
 	union sh_fpu_union fpu;
 };
 
-#define INIT_MMAP \
-{ &init_mm, 0, 0, NULL, PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  {						\
 	sizeof(init_stack) + (long) &init_stack, /* sp */	\
 	0,					 /* pc */	\
include/asm-sparc/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-sparc/processor.h mmap-rb/include/asm-sparc/processor.h
@@ -91,9 +91,6 @@
 #define SPARC_FLAG_KTHREAD      0x1    /* task is a kernel thread */
 #define SPARC_FLAG_UNALIGNED    0x2    /* is allowed to do unaligned accesses */
 
-#define INIT_MMAP { &init_mm, (0), (0), \
-		    NULL, __pgprot(0x0) , VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  { \
 /* uwinmask, kregs, ksp, kpc, kpsr, kwim */ \
    0,        0,     0,   0,   0,    0, \
include/asm-sparc64/processor.h +0 -3
diff -urN 2.4.10pre4/include/asm-sparc64/processor.h mmap-rb/include/asm-sparc64/processor.h
@@ -85,9 +85,6 @@
 #define FAULT_CODE_ITLB		0x04	/* Miss happened in I-TLB		*/
 #define FAULT_CODE_WINFIXUP	0x08	/* Miss happened during spill/fill	*/
 
-#define INIT_MMAP { &init_mm, 0xfffff80000000000, 0xfffff80001000000, \
-		    NULL, PAGE_SHARED , VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
-
 #define INIT_THREAD  {					\
 /* ksp, wstate, cwp, flags, current_ds, */ 		\
    0,   0,      0,   0,     KERNEL_DS,			\
include/linux/mm.h +24 -5
diff -urN 2.4.10pre4/include/linux/mm.h mmap-rb/include/linux/mm.h
@@ -11,6 +11,7 @@
 #include <linux/list.h>
 #include <linux/mmzone.h>
 #include <linux/swap.h>
+#include <linux/rbtree.h>
 
 extern unsigned long max_mapnr;
 extern unsigned long num_physpages;
@@ -50,10 +51,7 @@
 	pgprot_t vm_page_prot;		/* Access permissions of this VMA. */
 	unsigned long vm_flags;		/* Flags, listed below. */
 
-	/* AVL tree of VM areas per task, sorted by address */
-	short vm_avl_height;
-	struct vm_area_struct * vm_avl_left;
-	struct vm_area_struct * vm_avl_right;
+	rb_node_t vm_rb;
 
 	/*
 	 * For areas with an address space and backing store,
@@ -490,7 +488,7 @@
 extern void unlock_vma_mappings(struct vm_area_struct *);
 extern void insert_vm_struct(struct mm_struct *, struct vm_area_struct *);
 extern void __insert_vm_struct(struct mm_struct *, struct vm_area_struct *);
-extern void build_mmap_avl(struct mm_struct *);
+extern void build_mmap_rb(struct mm_struct *);
 extern void exit_mmap(struct mm_struct *);
 
 extern unsigned long get_unmapped_area(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
@@ -516,6 +514,22 @@
 
 extern unsigned long do_brk(unsigned long, unsigned long);
 
+static inline void __vma_unlink(struct mm_struct * mm, struct vm_area_struct * vma, struct vm_area_struct * prev)
+{
+	prev->vm_next = vma->vm_next;
+	rb_erase(&vma->vm_rb, &mm->mm_rb);
+	if (mm->mmap_cache == vma)
+		mm->mmap_cache = prev;
+}
+
+static inline int can_vma_merge(struct vm_area_struct * vma, unsigned long vm_flags)
+{
+	if (!vma->vm_file && vma->vm_flags == vm_flags)
+		return 1;
+	else
+		return 0;
+}
+
 struct zone_t;
 /* filemap.c */
 extern void remove_inode_page(struct page *);
@@ -562,6 +576,11 @@
 {
 	unsigned long grow;
 
+	/*
+	 * vma->vm_start/vm_end cannot change under us because the caller is required
+	 * to hold the mmap_sem in write mode. We need to get the spinlock only
+	 * before relocating the vma range ourself.
+	 */
 	address &= PAGE_MASK;
 	grow = (vma->vm_start - address) >> PAGE_SHIFT;
 	if (vma->vm_end - address > current->rlim[RLIMIT_STACK].rlim_cur ||
include/linux/rbtree.h +133 -0

133 lines not on this page · raw message

include/linux/sched.h +3 -8
diff -urN 2.4.10pre4/include/linux/sched.h mmap-rb/include/linux/sched.h
@@ -13,6 +13,7 @@
 #include <linux/types.h>
 #include <linux/times.h>
 #include <linux/timex.h>
+#include <linux/rbtree.h>
 
 #include <asm/system.h>
 #include <asm/semaphore.h>
@@ -199,12 +200,9 @@
 /* Maximum number of active map areas.. This is a random (large) number */
 #define MAX_MAP_COUNT	(65536)
 
-/* Number of map areas at which the AVL tree is activated. This is arbitrary. */
-#define AVL_MIN_MAP_COUNT	32
-
 struct mm_struct {
 	struct vm_area_struct * mmap;		/* list of VMAs */
-	struct vm_area_struct * mmap_avl;	/* tree of VMAs */
+	rb_root_t mm_rb;
 	struct vm_area_struct * mmap_cache;	/* last find_vma result */
 	pgd_t * pgd;
 	atomic_t mm_users;			/* How many users with user space? */
@@ -236,13 +234,10 @@
 
 #define INIT_MM(name) \
 {			 				\
-	mmap:		&init_mmap, 			\
-	mmap_avl:	NULL, 				\
-	mmap_cache:	NULL, 				\
+	mm_rb:		RB_ROOT,			\
 	pgd:		swapper_pg_dir, 		\
 	mm_users:	ATOMIC_INIT(2), 		\
 	mm_count:	ATOMIC_INIT(1), 		\
-	map_count:	1, 				\
 	mmap_sem:	__RWSEM_INITIALIZER(name.mmap_sem), \
 	page_table_lock: SPIN_LOCK_UNLOCKED, 		\
 	mmlist:		LIST_HEAD_INIT(name.mmlist),	\
kernel/fork.c +1 -3
diff -urN 2.4.10pre4/kernel/fork.c mmap-rb/kernel/fork.c
@@ -131,7 +131,6 @@
 	flush_cache_mm(current->mm);
 	mm->locked_vm = 0;
 	mm->mmap = NULL;
-	mm->mmap_avl = NULL;
 	mm->mmap_cache = NULL;
 	mm->map_count = 0;
 	mm->rss = 0;
@@ -198,8 +197,7 @@
 			goto fail_nomem;
 	}
 	retval = 0;
-	if (mm->map_count >= AVL_MIN_MAP_COUNT)
-		build_mmap_avl(mm);
+	build_mmap_rb(mm);
 
 fail_nomem:
 	flush_tlb_mm(current->mm);
lib/Makefile +1 -1
diff -urN 2.4.10pre4/lib/Makefile mmap-rb/lib/Makefile
@@ -10,7 +10,7 @@
 
 export-objs := cmdline.o dec_and_lock.o rwsem-spinlock.o rwsem.o
 
-obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o
+obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o rbtree.o
 
 obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
lib/rbtree.c +293 -0

293 lines not on this page · raw message

mm/filemap.c +16 -13
diff -urN 2.4.10pre4/mm/filemap.c mmap-rb/mm/filemap.c
@@ -1798,6 +1798,7 @@
 	unsigned long end, int behavior)
 {
 	struct vm_area_struct * n;
+	struct mm_struct * mm = vma->vm_mm;
 
 	n = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
 	if (!n)
@@ -1810,12 +1811,12 @@
 		get_file(n->vm_file);
 	if (n->vm_ops && n->vm_ops->open)
 		n->vm_ops->open(n);
-	lock_vma_mappings(vma);
-	spin_lock(&vma->vm_mm->page_table_lock);
 	vma->vm_pgoff += (end - vma->vm_start) >> PAGE_SHIFT;
+	lock_vma_mappings(vma);
+	spin_lock(&mm->page_table_lock);
 	vma->vm_start = end;
-	__insert_vm_struct(current->mm, n);
-	spin_unlock(&vma->vm_mm->page_table_lock);
+	__insert_vm_struct(mm, n);
+	spin_unlock(&mm->page_table_lock);
 	unlock_vma_mappings(vma);
 	return 0;
 }
@@ -1824,6 +1825,7 @@
 	unsigned long start, int behavior)
 {
 	struct vm_area_struct * n;
+	struct mm_struct * mm = vma->vm_mm;
 
 	n = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
 	if (!n)
@@ -1838,10 +1840,10 @@
 	if (n->vm_ops && n->vm_ops->open)
 		n->vm_ops->open(n);
 	lock_vma_mappings(vma);
-	spin_lock(&vma->vm_mm->page_table_lock);
+	spin_lock(&mm->page_table_lock);
 	vma->vm_end = start;
-	__insert_vm_struct(current->mm, n);
-	spin_unlock(&vma->vm_mm->page_table_lock);
+	__insert_vm_struct(mm, n);
+	spin_unlock(&mm->page_table_lock);
 	unlock_vma_mappings(vma);
 	return 0;
 }
@@ -1850,6 +1852,7 @@
 	unsigned long start, unsigned long end, int behavior)
 {
 	struct vm_area_struct * left, * right;
+	struct mm_struct * mm = vma->vm_mm;
 
 	left = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
 	if (!left)
@@ -1873,16 +1876,16 @@
 		vma->vm_ops->open(left);
 		vma->vm_ops->open(right);
 	}
-	lock_vma_mappings(vma);
-	spin_lock(&vma->vm_mm->page_table_lock);
 	vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;
+	vma->vm_raend = 0;
+	lock_vma_mappings(vma);
+	spin_lock(&mm->page_table_lock);
 	vma->vm_start = start;
 	vma->vm_end = end;
 	setup_read_behavior(vma, behavior);
-	vma->vm_raend = 0;
-	__insert_vm_struct(current->mm, left);
-	__insert_vm_struct(current->mm, right);
-	spin_unlock(&vma->vm_mm->page_table_lock);
+	__insert_vm_struct(mm, left);
+	__insert_vm_struct(mm, right);
+	spin_unlock(&mm->page_table_lock);
 	unlock_vma_mappings(vma);
 	return 0;
 }
mm/mlock.c +3 -3
diff -urN 2.4.10pre4/mm/mlock.c mmap-rb/mm/mlock.c
@@ -36,9 +36,9 @@
 		get_file(n->vm_file);
 	if (n->vm_ops && n->vm_ops->open)
 		n->vm_ops->open(n);
+	vma->vm_pgoff += (end - vma->vm_start) >> PAGE_SHIFT;
 	lock_vma_mappings(vma);
 	spin_lock(&vma->vm_mm->page_table_lock);
-	vma->vm_pgoff += (end - vma->vm_start) >> PAGE_SHIFT;
 	vma->vm_start = end;
 	__insert_vm_struct(current->mm, n);
 	spin_unlock(&vma->vm_mm->page_table_lock);
@@ -100,13 +100,13 @@
 		vma->vm_ops->open(left);
 		vma->vm_ops->open(right);
 	}
+	vma->vm_raend = 0;
+	vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;
 	lock_vma_mappings(vma);
 	spin_lock(&vma->vm_mm->page_table_lock);
-	vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;
 	vma->vm_start = start;
 	vma->vm_end = end;
 	vma->vm_flags = newflags;
-	vma->vm_raend = 0;
 	__insert_vm_struct(current->mm, left);
 	__insert_vm_struct(current->mm, right);
 	spin_unlock(&vma->vm_mm->page_table_lock);
mm/mmap.c +297 -142

578 lines not on this page · raw message

mm/mmap_avl.c +0 -374

374 lines not on this page · raw message

mm/mprotect.c +79 -26

215 lines not on this page · raw message

mm/mremap.c +62 -13

90 lines not on this page · raw message

It's also here:

	ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.10pre4/mmap-rb-7

Andrea