memory overcommitment

memory overcommitment

[Nicolas Devillard]

Dear all:

I can allocate up to 2 gigs of memory on a Linux box with 256 megs of
actual RAM + swap. Having browsed through pages and pages of linux-kernel
mailing-lists archives, I found out a thread discussing that with the
usual pros and cons, but could not find anything done about it. Ah, and I
know the standard answer: ulimit or limit would do the job, but they do
not apply system-wide.

The usual story of over-commitment compares memory allocation to
airplane companies, but in this case something goes wrong: the kernel
actually knows that it has only 256 megs, why does it commit itself to
promise more than 8 times this amount to any normal user requesting it??
A company selling 100 tickets for a 12-seat plane would have serious
problems I guess. It is Ok to overbook, but what are you doing exactly
when all passengers show up at the counter, especially when you have
overbooked by a factor 8 or so?

In this case, I found out that once I start touching the 2 generously
allocated gigs of memory, RAM goes away, then swap, then daemons start
dying one by one and the machine freezes to the point of unusability. More
than a single memory allocation problem or policy, it is a serious threat
to security, because it allows to kill dameons for any user.

Anything done about it? Some references I may have missed about this
point? Someone working on it? An easy quickfix maybe??

Thanks for helping,
Nicolas

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: memory overcommitment

[Stephen C. Tweedie]

Hi,

On Mon, 17 Aug 1998 10:46:24 +0200 (MET DST), Nicolas Devillard
<ndevilla@mygale.org> said:

> Dear all:
> I can allocate up to 2 gigs of memory on a Linux box with 256 megs of
> actual RAM + swap. Having browsed through pages and pages of linux-kernel
> mailing-lists archives, I found out a thread discussing that with the
> usual pros and cons, but could not find anything done about it. Ah, and I
> know the standard answer: ulimit or limit would do the job, but they do
> not apply system-wide.

> The usual story of over-commitment compares memory allocation to
> airplane companies, but in this case something goes wrong: the kernel
> actually knows that it has only 256 megs, why does it commit itself to
> promise more than 8 times this amount to any normal user requesting it??
> A company selling 100 tickets for a 12-seat plane would have serious
> problems I guess. It is Ok to overbook, but what are you doing exactly
> when all passengers show up at the counter, especially when you have
> overbooked by a factor 8 or so?

The short answer is "don't do that, then"!  

Preventing overbooking is not actually possible given Linux's unified
memory model.  Even if the memory commitment fits into combined
ram+swap, future non-pageable memory allocations can overrun.
Networking, the filesystem, the VM and so on all take up non-pageable
memory.  Forking a process takes memory; mmaping() a file takes memory,
both for the internal descriptors and for the page tables, even though
there is no accounting for that memory against committed resources.

The only way we can make the commitment guarantee is to limit total
allocated memory to the size of swap space.  That's just contrary to the
Linux way of doing things, as we have users with less swap space than
physical memory, without any swap at all, or with programs which
internally overallocate enormously but which then fail to use all of the
allocated space.  Fortran codes are notorious for having huge default
arrays of which only a tiny proportion gets used, but there are many
other examples too.

Finally, even if we _do_ enforce memory commitments, that's still a
denial-of-service attack, since a user which grabs all memory is still
preventing other users or other system processes from getting more.

> In this case, I found out that once I start touching the 2 generously
> allocated gigs of memory, RAM goes away, then swap, then daemons start
> dying one by one and the machine freezes to the point of unusability. More
> than a single memory allocation problem or policy, it is a serious threat
> to security, because it allows to kill dameons for any user.

Exactly.  For all of the reasons above, I don't think we _can_ prevent
memory overcommit.  The real issue is how to deal with it: letting
normal daemons get anihilated because of a runaway user process is not a
good thing.  Rik has already posted an out-of-memory patch to this list
which attempts to do more intelligent killing of processes, and Alan Cox 
has implemented the basis of a per-user resource limiting feature which
will allow us to more rigorously enforce the limiting of intangible,
non-pageable data structures implicitly requested by a user.

> Anything done about it? Some references I may have missed about this
> point? Someone working on it? An easy quickfix maybe??

If you can suggest a good algorithm for selecting processes to kill,
we'd love to hear about it.  The best algorithm will not be the same for
all users.

--Stephen
 
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: memory overcommitment

[Chris Atenasio]

> If you can suggest a good algorithm for selecting processes to kill,
> we'd love to hear about it.  The best algorithm will not be the same for
> all users.

How bout: if(no_more_ram) kill(process_using_most_ram());

Of course to be useful it would have to add together the usage of multiple
instances of a program of the same uid(and then kill all of them too!).
Furthermore you might even want to kill uid 0 progs last.  This way hopefully an
attacker mallocing way too much or starting a fork bomb would be the one that
gets shafted.  (Maybe even write an interface to pass the offending uid to a
userspace program which can then invalidate that user account, send mail, do
cool things etc.)  Then what if you(the admin)C do something evil?
Well... don't!

- Chris
--------------------------------------------------------------------------------
Chris Atenasio (chrisa@ultranet.com) -- Friends dont let friends use Windows.
Send me mail with subject "send pgp key" or "word of the day" for autoresponse.


--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: memory overcommitment

[Stephen C. Tweedie]

Hi,

On Tue, 18 Aug 1998 11:52:06 -0400 (EDT), Chris Atenasio
<root@lilo.dyn.ml.org> said:

>> If you can suggest a good algorithm for selecting processes to kill,
>> we'd love to hear about it.  The best algorithm will not be the same for
>> all users.

> How bout: if(no_more_ram) kill(process_using_most_ram());

Very simplistic: on many systems, that will mean starting gcc takes out
the X server. :-(

> Of course to be useful it would have to add together the usage of
> multiple instances of a program of the same uid(and then kill all of
> them too!).  Furthermore you might even want to kill uid 0 progs last.

Certainly.

One thing on the agenda for consideration in 2.3 is resident set size
limits and quotas, which will allow us to cleanly reserve enough swap
and physical memory for specific uses.

--Stephen
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: memory overcommitment

[Nicolas Devillard]

On Mon, 17 Aug 1998, Stephen C. Tweedie wrote:
>
> The short answer is "don't do that, then"!  

Well... I certainly don't. The OS does it for me, which is precisely what
I want to avoid! I allocate N megs of memory, not because I use a system
function which does it implicitly (like fork() does), but because I want
this memory to store data and work with it. If the system cannot give me N
megs of memory, better tell me immediately with a NULL returned by
malloc() and an ENOMEM (as described in the man page, BTW), than tell me:
Ok, here's your pointer, so that I start working on my data and then
suddenly... crash. It's not that I am working on making Linux fly planes
or what, but when you start having data the size of a gig you realize it
will take some time to process it out completely. You certainly want to
know ASAP if your machine has enough memory or not, you don't want to wait
48h to realize everything has crashed on the machine during the week-end,
including 'inetd' which means "take your car and go see by yourself". :-)

Why not separate allocators into two classes: lazy ones doing allocation
with overcommit, and the strong ones returning pointers to certified
memory (i.e. good old memory reserved for this process only)? Don't ask me
how to do it, you're the expert, I'm not :-)

> If you can suggest a good algorithm for selecting processes to kill,
> we'd love to hear about it.  The best algorithm will not be the same for
> all users.

Killing processes randomly is maybe one way to solve the problem,
certainly not the only one. Once you have cleared all solutions and come
to the conclusion that this is the only good one, let's go for it. For my
applications, I found out that the simplest way to allocate huge amounts
is to open enough temporary files on the user's disk, fill them up with
zeroes and mmap() them. This way, I get way past the physical memory, and
because I am never using the whole allocated stuff simultaneously, these
files are paged by the OS invisibly in a much more efficient way than I
could do. It is certainly slow, but still very reasonable, and avoids 
quite some headaches in programming.

Cheers
Nicolas

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: memory overcommitment

[Stephen C. Tweedie]

Hi,

On Tue, 18 Aug 1998 16:34:01 +0000 ( ), Nicolas Devillard
<ndevilla@mygale.org> said:

> On Mon, 17 Aug 1998, Stephen C. Tweedie wrote:
>> 
>> The short answer is "don't do that, then"!  

> Well... I certainly don't. The OS does it for me, which is precisely what
> I want to avoid! I allocate N megs of memory, not because I use a system
> function which does it implicitly (like fork() does), but because I want
> this memory to store data and work with it. If the system cannot give me N
> megs of memory, better tell me immediately with a NULL returned by
> malloc() and an ENOMEM (as described in the man page, BTW), than tell me:
> Ok, here's your pointer, so that I start working on my data and then
> suddenly... crash. 

As I said, the only way to do this is to writable private restrict
allocations to the size of available swap.  Otherwise, if you include
physical memory in the calculation, you can lose out: the kernel needs
to allocate physical memory for networking, page tables, stack space
etc.  There simply isn't any way around this.

> It's not that I am working on making Linux fly planes or what, but
> when you start having data the size of a gig you realize it will take
> some time to process it out completely. 

Then initialise the memory after malloc; you know the pages are there by
that stage. 

There are also lots of programs which allocate a gig of memory and only
use a tiny fraction of it.  We don't want them all to suddenly start
failing.  You can't have it both ways!

>> If you can suggest a good algorithm for selecting processes to kill,
>> we'd love to hear about it.  The best algorithm will not be the same for
>> all users.

> Killing processes randomly is maybe one way to solve the problem,
> certainly not the only one. 

Umm, killing inetd?  sendmaild?  init??!!

> For my applications, I found out that the simplest way to allocate
> huge amounts is to open enough temporary files on the user's disk,
> fill them up with zeroes and mmap() them. This way, I get way past the
> physical memory, and because I am never using the whole allocated
> stuff simultaneously, these files are paged by the OS invisibly in a
> much more efficient way than I could do. It is certainly slow, but
> still very reasonable, and avoids quite some headaches in programming.

Yep, that's common practice: essentially a writable mmap acts like
allocating your own swap file, which is an entirely reasonable thing to
do if you don't know in advance whether your data set will fit into the
amount of true swap present.

--Stephen
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: memory overcommitment

[Nicolas Devillard]

On Wed, 19 Aug 1998, Stephen C. Tweedie wrote:
> 
> Then initialise the memory after malloc; you know the pages are there by
> that stage. 

That is no solution. Futhermore, if other processes are also touching
overcommitted memory, the initialization might just crash the machine.
What I'm saying is: if malloc() does not tell me it has a tough life
finding free memory, and just returns space generously, I have no way to
know it by myself (at least: no safe way).
What about a system call just before a series of malloc() to tell the OS
you are actually going to use this allocated memory?
This could even be set as a default for machines used as number-crunchers,
you will need lots of RAM and disk space on these anyway.

> There are also lots of programs which allocate a gig of memory and only
> use a tiny fraction of it.  We don't want them all to suddenly start
> failing.  You can't have it both ways!

Hard to believe there is no way to have both. Simply because a memory
allocation done by a forking Netscape is not the same as one done by a
developper in need of memory to process data. At least give a developper a
chance to ensure the promised memory is really there! :-)

> Umm, killing inetd?  sendmaild?  init??!!

Killing processes does not look like a solution. My feeling is: you are
entering an endless world full of nightmares if you want to implement an
intelligent daemon trying to figure out how to kill user processes.
Everyone has different requirements about how to do that, and you will
have a hard time putting this up in a simple way for the sysadmin to set
it up correctly (if there is any way to do that). Looks like a dead-end.

Let me try to put up user requirements on that one: 

- when I get allocated memory, I must be sure that it is really
  allocated and not faked, because I am 100% sure that I will use it.
  Because I know that in advance, it should not be too hard to
  communicate it to the OS by any system call or resource parameter you
  wish.
- if no more memory is available, I would like to get a message or a
  signal or whatever, telling me (politely :-) that I'm too greedy. This
  way, I know what to do: kill all netscapes, xemacs, even X if I really
  need memory, or buy more RAM, make more swap, etc. I do not fell that
  kind of decision should not be taken on the fly by any automatic
  procedure (especially to buy some RAM, I like to go by myself :-).

Cheers
Nicolas

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org