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

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

[Rick Hohensee]

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

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

BROWNNOSE
No, I have nothing to say about malloc/mmap/etc. I just want to add some
balancing positiveness to offset my usual polemics. Torvalds harps on
optimizing for the common case all the time. This little voice with a
faint scandanavian accent in the back of my head keeps saying "optimize
for the common case". It is a wise little voice. The common case is
usually beyond the ken of a compiler, it's something a human has to
know, it works, can pay off huge, and works with anything from assembly
to Bash. 
END BROWNNOSE   
RESUME FLAMEBAIT

Rick Hohensee
						www.clienux.com

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

[David Luyer]

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

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

[Chris Wedgwood]

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

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

[Andrea Arcangeli]

On Mon, Aug 06, 2001 at 04:41:21PM +1000, David Luyer wrote:
> 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

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

[Jakub Jelinek]

On Mon, Aug 06, 2001 at 10:59:04AM +0200, Andrea Arcangeli wrote:
> On Mon, Aug 06, 2001 at 04:41:21PM +1000, David Luyer wrote:
> > 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

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

[Andrea Arcangeli]

On Mon, Aug 06, 2001 at 06:30:03AM -0400, Jakub Jelinek wrote:
> On Mon, Aug 06, 2001 at 10:59:04AM +0200, Andrea Arcangeli wrote:
> > On Mon, Aug 06, 2001 at 04:41:21PM +1000, David Luyer wrote:
> > > 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

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

[Jakub Jelinek]

On Mon, Aug 06, 2001 at 12:49:52PM +0200, Andrea Arcangeli wrote:
> On Mon, Aug 06, 2001 at 06:30:03AM -0400, Jakub Jelinek wrote:
> > On Mon, Aug 06, 2001 at 10:59:04AM +0200, Andrea Arcangeli wrote:
> > > On Mon, Aug 06, 2001 at 04:41:21PM +1000, David Luyer wrote:
> > > > 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.

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

	Jakub

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

[Andrea Arcangeli]

On Mon, Aug 06, 2001 at 07:01:24AM -0400, Jakub Jelinek wrote:
> On Mon, Aug 06, 2001 at 12:49:52PM +0200, Andrea Arcangeli wrote:
> > On Mon, Aug 06, 2001 at 06:30:03AM -0400, Jakub Jelinek wrote:
> > > On Mon, Aug 06, 2001 at 10:59:04AM +0200, Andrea Arcangeli wrote:
> > > > On Mon, Aug 06, 2001 at 04:41:21PM +1000, David Luyer wrote:
> > > > > 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.
> 
> 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

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

[Linus Torvalds]

On Mon, 6 Aug 2001, Jakub Jelinek wrote:
>
> 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

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

[Alan Cox]

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

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

[Chris Wedgwood]

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

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

[Jakub Jelinek]

On Mon, Aug 06, 2001 at 12:49:52PM +0200, Andrea Arcangeli wrote:
> 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

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

[Linus Torvalds]

On Mon, 6 Aug 2001, Andrea Arcangeli wrote:
>
> 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

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

[David S. Miller]

Andrea Arcangeli writes:
 > 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
davem@redhat.com

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

[Chris Wedgwood]

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

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

[Andrea Arcangeli]

On Mon, Aug 06, 2001 at 02:20:42AM -0700, David S. Miller wrote:
> 
> Andrea Arcangeli writes:
>  > 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.

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

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

[Chris Wedgwood]

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

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

[Andrea Arcangeli]

On Tue, Aug 07, 2001 at 12:26:50AM +1200, Chris Wedgwood wrote:
> 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

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

[Chris Wedgwood]

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

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

[Andrea Arcangeli]

On Tue, Aug 07, 2001 at 12:45:10AM +1200, Chris Wedgwood wrote:
> 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

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

[David S. Miller]

Andrea Arcangeli writes:
 > On Tue, Aug 07, 2001 at 12:45:10AM +1200, Chris Wedgwood wrote:
 > > 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
davem@redhat.com

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

[Andrea Arcangeli]

On Mon, Aug 06, 2001 at 06:06:14AM -0700, David S. Miller wrote:
> 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

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

[Linus Torvalds]

On Mon, 6 Aug 2001, Andrea Arcangeli wrote:
>
> On Mon, Aug 06, 2001 at 06:06:14AM -0700, David S. Miller wrote:
> > 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.

> 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

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

[Linus Torvalds]

On Mon, 6 Aug 2001, Andrea Arcangeli wrote:

> On Tue, Aug 07, 2001 at 12:26:50AM +1200, Chris Wedgwood wrote:
> > 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

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

[David Luyer]

On 06 Aug 2001 10:20:15 -0700, Linus Torvalds wrote:
> 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.
-- 
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

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

[Anton Altaparmakov]

At 18:20 06/08/2001, Linus Torvalds wrote:

>On Mon, 6 Aug 2001, Andrea Arcangeli wrote:
>
> > On Tue, Aug 07, 2001 at 12:26:50AM +1200, Chris Wedgwood wrote:
> > > 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.

Is it possible that is has something to do with what "man malloc" on my 
machine says in the notes section:

---quote from man page, glibc 2.2.3-14 on RedHat 7.something---
Recent versions of Linux libc (later than 5.4.23) and GNU libc (2.x) 
include a malloc implementation which is tunable via environment variables. 
When MALLOC_CHECK_ is set, a special (less efficient) implementation is 
used which is designed to be tolerant against simple errors, such as double 
calls of free() with the same argument, or overruns of a single byte 
(off-by-one bugs). Not all such errors can be proteced against, however, 
and memory leaks can result. If MALLOC_CHECK_ is set to 0, any detected 
heap corruption is silently ignored; if set to 1, a diag­nostic is printed 
on stderr; if set to 2, abort() is called immediately. This can be useful 
because otherwise a crash may happen much later, and the true cause for the 
problem is then very hard to track down.
---eoq---

That sounds like the kind of stuff Electric Fence would be doing, doesn't it?

Best regards,

Anton


-- 
   "Nothing succeeds like success." - Alexandre Dumas
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Linux NTFS Maintainer / WWW: http://linux-ntfs.sf.net/
ICQ: 8561279 / WWW: http://www-stu.christs.cam.ac.uk/~aia21/

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

[Rik van Riel]

On Mon, 6 Aug 2001, David S. Miller wrote:
> Andrea Arcangeli writes:
>  > 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/

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

[Linus Torvalds]

On Mon, 6 Aug 2001, Rik van Riel wrote:

> On Mon, 6 Aug 2001, David S. Miller wrote:
> > Andrea Arcangeli writes:
> >  > 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