I love articles like this. I always learn something new. I must admit that I did think that malloc would use VM if necessary hence giving a potentially "unlimited" address space, but I guess it is nice to have that cemented rather than theorized.
Can we ever really count on memory being allocated to RAM? I think not (it's against the kernel/user buffer right?), but it's good to know these things.
Of course: I attempt to always be in a learning phase so if anyone can expand (or elaborate) then I'd appreciate it :)
I must admit that I did think that malloc would use VM if necessary hence giving a potentially "unlimited" address space
There's no distinction between "VM" and non "VM" as far as malloc is concerned. From the perspective of the process, it's one big, flat address space. It's always "virtual", because the values of the pointers do not necessarily equal the physical layout of the memory that is directly backed by RAM.
Most systems have calls that tell the OS "this page must stay in physical memory". On Unix-like systems, "man mlock" probably tells you more. On Windows, I think the equivalent is called VirtualLock.
Everything's ok until you try to write to more memory than is available. At that point, either your program segfaults, or Linux's Out-Of-Memory (OOM) Killer is invoked and kills a random process (not necessarily the offending process).
You should instruct the OOM Killer to not kill PostgreSQL.
Memory is a global resource, even if you didn't overcommit the process getting the allocation failure is not guaranteed to be the misbehaving one, it's just the unlucky process that did the first allocation after all the memory was gone (this is also why handling allocation errors in your application is usually impossible, even without an overcommitting kernel).
It's not something that's easy to develop a general solution to. Maybe the process that's using a lot of RAM is not runaway, and is mission-critical. Maybe it is a runaway process and something else is mission-critical.
The most 'fair' way to go about it is to just kill a random process. That skits the whole issue.
I altered the program to first allocate 64G then go through and write on each page of the allocation on my 16G machine, dropped my swap partition.
After suitable screwing around to keep gcc from optimizing away the writes, it goes a bit like this…
jim@gvdev:~$ ./fail
Before
Allocated 1 GB
Allocated 2 GB
...
Allocated 64 GB
After
Writing in 0 GB
Writing in 1 GB
...
Writing in 15 GB
... rather long delay here...
Write failed: Broken pipe
upstairs:~ jim$ <----- bad news here, notice the machine.
upstairs:~ jim$ slogin gvdev.XXXXX.net
ssh: connect to host gvdev.XXXXX.net port 22: Network is unreachable
… so now I have to get back in "going out" clothes, go downstairs, and drive over to gvdev and reboot it.
The linux Out Of Memory killer would have activated (if not disabled). This program derives a 'score' for each program, based on a number of statistics, and kills the process with the highest score. Although it usually makes the right choice, sometimes it can kill innocent programs.
It was worse than a dead sshd. Looks like something kernel-ish died badly. There was one more cron message in the syslog after this, but then nothing until I rebooted. Console unresponsive, no ping answering.
Nov 2 21:29:33 gvdev kernel: [15115318.546376] fail[17150]:
segfault at 7fffe9cbc1e0 ip 00000000004006fe sp 00007fffe9cbb1d0
error 4 in fail[400000+1000]
This is a problem with virtual machines vendors such as Linode where the configured swap space is usually tiny by default... It's much better to provide more swap (At least as much as RAM size) and see the performances start to deteriorate as a sign of alarm of overcommit, instead of having random processes killed.
That depends on what you mean "more memory than you have". If it's more physical RAM than is currently available, not necessarily a problem - some other processes can be pushed out of RAM into swap. If it's more than that, some pages can be discarded because they're backed by binaries on disk. If it's more than that, some processes can be killed. If it's more than that, really bad things happen.
The problem is that there's no good way to differentiate between a process that merely wants more VM that it'll never touch and a process that wants actual RAM. In theory, every fork() should double your VM requirements - in practice, almost all are immediately followed by an exec() and the previous allocations are irrelevant. Do you fail fork() because you can't guarantee you can back every modified page in the new process? If not, why should you fail malloc() because you can't guarantee you can back it? There's no correct answer, and Linux lets you control which answer you want via /proc/sys/vm/overcommit_memory .
Actually on solaris, the fork does OOM a java VM. So while this is a pragmatic solution on linux, its also a false promise which will paper over some transient memory requirements while leaving a huge gap in regards to realistic resource expectations. Unfortunately this problem is magnified when using virtual OS instances, and shitty hardware.
Zero-Fill on Demand - All new pages map to a single zero "frame" in physical memory. In this case, you don't get any memory until you write to the page, at which time the OS steps in and allocates you a page of all zeros
EDIT: this means if the kernel can't allocate more memory when you write then the kernel has a decision to make; kill you, or kill someone else to get more memory.
> We just need to be careful because malloc returning successfully does not always mean that we can use the requested memory.
this is not really true and it's dangerous to think this way (IMO).
one of the awesome things about virtual memory is you can "use" more memory than you actually have. if you only have 4GB of physical pages on your system and you allocate 18GB of virtual memory, things will be fine until you write to more pages than you have.
at this point, things are still fine! the memory manager will pick some pages (usually ones that haven't been accessed in a while) and page them out to a paging file. this behavior is transparent to your application. when your application tries to access those pages, the memory manager will bring those pages back in. if it can't bring the pages back in because all the pages are taken, it will choose some pages to put back into the page file. and so on ...
"so what happens when the page file is full?" well, modern operating systems have a page file that grows. so really, "what happens when the page file is uncomfortably large" is the question, and the answer there is the kernel will start killing tasks, and the first on the chopping block will probably be yours.
some platforms allow you to register for notification from the memory manager that there is a lot of pressure for physical pages or virtual addresses. the problem with trying to gain awareness like this is that the pressure on memory is generally totally outside your control. if the memory manager tells your app 'hey, free any memory you're not using' you are going to say 'oh yeah right i just had these hundreds of megabytes just sitting around but now that you mention it i probably should release them'. uh huh.
imo short takeaway:
1. check if malloc is null because the behavior of the allocator is platform dependent.
2. if you get a non-null pointer from malloc, treat it is valid. there is nothing else you can do. perhaps touching it will make the kernel kill your task perhaps not! it could be because your app is using too much memory. it could be because the app next door is using too much memory! you can't know.
3. you should take an operating systems class from a university if you want to really explore this topic in depth
With an application using garbage collection it's quite easy to have hundreds of megabytes just sitting around, so I think it could be a good idea in some cases.
Yes, but my impression is that the set of conditions where this helps (you have memory pressure AND the runtime has lots of memory it can free up) is rather rare. If you have memory pressure, that's usually the same time that the runtime is actually trying to make use of lots of memory.
IIRC, Android provides something along these lines (as does Windows Phone 7.1), and when you get under memory pressure (common on Honeycomb-based tablets) you end up with thousands of these notifications, each freeing up 1KB or 2KB when you really need to free up tens of megabytes (which you can only do by serializing and terminating an application).
aha! true, yes. I hadn't considered that case. then it would make sense. I suppose another case would be if you were maintaining some kind of data cache that could either be discarded or flushed to disk. so maybe these mechanisms are more useful than I thought.
Even after having the occasional run-in with the OOM killer and having to drive into work at 3am because sshd was among the casualties, I can't see thwarting the OS's virtual memory system like this.
Besides, if you're really that worried about uptime that falling victim to the OOM killer is an unacceptable risk, you should be preparing for surprise hardware failure too, which in my experience is much more likely to happen anyway and can be just as fatal to your "invincible" process.
>> and the first on the chopping block will probably be yours.
Unfortunately this often won't be the case. The algorithm used for selection in the oom killer will try to preserve processes which have accumulated higher CPU time - on a typical server, the most active process will often be the one consuming all the memory.
This can lead to a painful situation where critical processes like sshd, or your shell, are killed off to allow more space for the runaway app. Quickly leading to a hard reset being the only recovery option.
This guy is wrong, for the record. The default behavior of malloc on linux involves kernel magic to decide whether to allocate the memory. Since he wasn't actually writing any data to any of his ram, it didn't fail until he ran out of address space. If he'd actually used the memory, it would have failed sooner.
The other, bigger problem is his assumption that all linux installations work like this. Frequently vm.overcommit_memory is set to disable malloc calls for more than the available amount of memory, which means the oom-killer never gets inolved. He's making a ton of dangerous assumptions based on tooling around with code instead of reading the documentation on the matter (i.e. malloc(3)).
Of course, it's basically a wrapper around malloc. All allocated memory is subject to this behaviour: malloc/calloc, forked "copy-on-write" memory, mmaps and statically allocated segments (especially the stack).
In a system with MMU all allocating memory does is tell the kernel to not give you a segfault when you access some range of virtual addresses. To actually materialize a virtual page you have to access it.
>because calloc zeros the memory and therefore writes to each page.
One does not imply the other. Internally what the kernel can do is link the page address it gives you to the zero page and mark it as copy on write. Only when you actually write to it will it allocate an actual page to back it. Only if your libc implements calloc as malloc+memset would this be a problem. Does glibc do that?
In fact the copy on write is probably also done on malloc as well. Even though the manpage implies different behavior (malloc doesn't guarantee setting the memory to 0, while calloc does) I don't think any sane kernel will give you someone else's free()'d memory. It would be a security leak.
>You won't get someone else's freed memory but you're quite likely to get your own back and in that case it won't necessarily be zeroed.
Surely the kernel never gives a process it's own pages back. It would keep an unneeded page around that could just be pointing to the zero page.
Reading your other comment I assume what you mean is that it is a two step process where the kernel always gives zero pages but glibc's malloc implementation keeps some stock of pages and will return them back in a malloc() after a free(). That way you're not guaranteed to get zero'd memory on every malloc() since not all of it comes straight from the kernel.
The calloc() implementation has checks for that and will do the clearing when the memory is coming from the glibc stock and not the kernel. But even in that case it's only doing clearing when the page is already in the process address space. So a process will always receive zero pages from the kernel, but the malloc() implementation is made more efficient by giving you back some of your own free()'d memory that from the kernel's point of view was never given back.
I didn't look in enough detail on the Linux side to see if it always gives a zero page reference, or does/doesn't clear out a fresh page when it's referenced based on how it was allocated and by whom. I could see that saving time but I can easily see just nuking a whole page being faster than the work of tracking and checking.
From the glibc side I believe you are exactly correct.
I wasn't sure why that would be the case. To me, the naïve answer would be that they wouldn't behave the same, as calloc is required to return cleared memory, meaning memset or similar. Saving time on allocation but clearing it on access would seem to require kernel-level access below that of the C library. So I took a look.
Interestingly, in glibc-2.15, the code for calloc (well, public_cALLOc) is longer than that for malloc. Most of that actually seems just to be doing magic to figure out when it actually needs to clear it. So in any cases where calloc is touching reused memory, it clears that itself. Otherwise, things end up at either mmapping MAP_ANONYMOUS or sbrking, which simply allocates pages that all get cleared on access (well, on write) anyway for security reasons.
Honestly I was surprised how much indirection and optimization there was. I knew that there were some clever things being done and they try to take advantage of processor features. But this stuff really does everything possible to avoid even a single unnecessary cycle. I'm impressed.
So in the general case, calloc might do some extra work. But where you're just callocing heaps and heaps (tee hee) it's not likely to. Strange, I could have sworn I just stumbled upon a case where someone claimed doing that was noticeably slower, but now I can't find it... was going to be very curious how that was the case. But after this romp I'm tired.
In addition to this guy having a total misunderstanding of how this worked and why it eventually failed ("control structures"?!") the article glosses over how this behavior relates to configuration options such as vm.overcommit... it doesn't even use the correct term (overcommit), so readers don't manage to even leave with the ability to rapidly learn more about the subject.
Yet, I have now been tricked into seeing it twice, as in addition to being on the HN home page for over 6 hours (with not that many upvotes, but still way too many) it was renamed by a moderator from the original title it was posted with ("Malloc never fails", weirdly in the opposite direction of the policy of "use the original title" that is normally cited for legitimizing renames) so you couldn't recognize "oh, this is that wrong article from earlier".
Worse, a somewhat informative comment on this site from the user "khm", one that links to a better article that discusses these issues with the right terminology an in context with the OOM killer, is marked [dead], caught by some spam filter or maybe even dowvoted/flagged to death by readers.
Extending my comment, I am almost sure that passing a small negative argument (which is converted to a large positive number) causes malloc to return NULL on Linux.
Makes me respect the early engineers and programmers who have put in great thought in building these blocks. Seriously, reading through all this in HTML5, Android, iOS world of today with IDE, code samples, every book and whole communities to help you, make me respect early programmers so much. They were the real risk takers to venture into something entirely unknown and created a whole new discipline which is empowering every existent discipline and creating many more.
Meta: The article itself is wrong as it was pointed out here. However, I learned a lot from the discussion around it. Should I upvote the submission or not?
49 comments
[ 3.0 ms ] story [ 107 ms ] threadOf course: I attempt to always be in a learning phase so if anyone can expand (or elaborate) then I'd appreciate it :)
There's no distinction between "VM" and non "VM" as far as malloc is concerned. From the perspective of the process, it's one big, flat address space. It's always "virtual", because the values of the pointers do not necessarily equal the physical layout of the memory that is directly backed by RAM.
It's terrible about this with PostgreSQL. The OOM Killer tends to thump the postmaster, not the offending backend.
Memory is a global resource, even if you didn't overcommit the process getting the allocation failure is not guaranteed to be the misbehaving one, it's just the unlucky process that did the first allocation after all the memory was gone (this is also why handling allocation errors in your application is usually impossible, even without an overcommitting kernel).
The most 'fair' way to go about it is to just kill a random process. That skits the whole issue.
After suitable screwing around to keep gcc from optimizing away the writes, it goes a bit like this…
… so now I have to get back in "going out" clothes, go downstairs, and drive over to gvdev and reboot it.The problem is that there's no good way to differentiate between a process that merely wants more VM that it'll never touch and a process that wants actual RAM. In theory, every fork() should double your VM requirements - in practice, almost all are immediately followed by an exec() and the previous allocations are irrelevant. Do you fail fork() because you can't guarantee you can back every modified page in the new process? If not, why should you fail malloc() because you can't guarantee you can back it? There's no correct answer, and Linux lets you control which answer you want via /proc/sys/vm/overcommit_memory .
EDIT: this means if the kernel can't allocate more memory when you write then the kernel has a decision to make; kill you, or kill someone else to get more memory.
this is not really true and it's dangerous to think this way (IMO).
one of the awesome things about virtual memory is you can "use" more memory than you actually have. if you only have 4GB of physical pages on your system and you allocate 18GB of virtual memory, things will be fine until you write to more pages than you have.
at this point, things are still fine! the memory manager will pick some pages (usually ones that haven't been accessed in a while) and page them out to a paging file. this behavior is transparent to your application. when your application tries to access those pages, the memory manager will bring those pages back in. if it can't bring the pages back in because all the pages are taken, it will choose some pages to put back into the page file. and so on ...
"so what happens when the page file is full?" well, modern operating systems have a page file that grows. so really, "what happens when the page file is uncomfortably large" is the question, and the answer there is the kernel will start killing tasks, and the first on the chopping block will probably be yours.
some platforms allow you to register for notification from the memory manager that there is a lot of pressure for physical pages or virtual addresses. the problem with trying to gain awareness like this is that the pressure on memory is generally totally outside your control. if the memory manager tells your app 'hey, free any memory you're not using' you are going to say 'oh yeah right i just had these hundreds of megabytes just sitting around but now that you mention it i probably should release them'. uh huh.
imo short takeaway:
1. check if malloc is null because the behavior of the allocator is platform dependent.
2. if you get a non-null pointer from malloc, treat it is valid. there is nothing else you can do. perhaps touching it will make the kernel kill your task perhaps not! it could be because your app is using too much memory. it could be because the app next door is using too much memory! you can't know.
3. you should take an operating systems class from a university if you want to really explore this topic in depth
IIRC, Android provides something along these lines (as does Windows Phone 7.1), and when you get under memory pressure (common on Honeycomb-based tablets) you end up with thousands of these notifications, each freeing up 1KB or 2KB when you really need to free up tens of megabytes (which you can only do by serializing and terminating an application).
Even after having the occasional run-in with the OOM killer and having to drive into work at 3am because sshd was among the casualties, I can't see thwarting the OS's virtual memory system like this.
Besides, if you're really that worried about uptime that falling victim to the OOM killer is an unacceptable risk, you should be preparing for surprise hardware failure too, which in my experience is much more likely to happen anyway and can be just as fatal to your "invincible" process.
Unfortunately this often won't be the case. The algorithm used for selection in the oom killer will try to preserve processes which have accumulated higher CPU time - on a typical server, the most active process will often be the one consuming all the memory.
This can lead to a painful situation where critical processes like sshd, or your shell, are killed off to allow more space for the runaway app. Quickly leading to a hard reset being the only recovery option.
The other, bigger problem is his assumption that all linux installations work like this. Frequently vm.overcommit_memory is set to disable malloc calls for more than the available amount of memory, which means the oom-killer never gets inolved. He's making a ton of dangerous assumptions based on tooling around with code instead of reading the documentation on the matter (i.e. malloc(3)).
malloc can fail, and you should deal with it well: http://ewontfix.com/3/
In a system with MMU all allocating memory does is tell the kernel to not give you a segfault when you access some range of virtual addresses. To actually materialize a virtual page you have to access it.
Just try the same program replacing malloc( 1 << 30 ) with calloc( 1, 1<<30).
One does not imply the other. Internally what the kernel can do is link the page address it gives you to the zero page and mark it as copy on write. Only when you actually write to it will it allocate an actual page to back it. Only if your libc implements calloc as malloc+memset would this be a problem. Does glibc do that?
In fact the copy on write is probably also done on malloc as well. Even though the manpage implies different behavior (malloc doesn't guarantee setting the memory to 0, while calloc does) I don't think any sane kernel will give you someone else's free()'d memory. It would be a security leak.
I just checked (see my reply to the parent) and it doesn't.
> In fact the copy on write is probably also done on malloc as well. [...] I don't think any sane kernel will give you someone else's free()'d memory
You won't get someone else's freed memory but you're quite likely to get your own back and in that case it won't necessarily be zeroed.
Surely the kernel never gives a process it's own pages back. It would keep an unneeded page around that could just be pointing to the zero page.
Reading your other comment I assume what you mean is that it is a two step process where the kernel always gives zero pages but glibc's malloc implementation keeps some stock of pages and will return them back in a malloc() after a free(). That way you're not guaranteed to get zero'd memory on every malloc() since not all of it comes straight from the kernel.
The calloc() implementation has checks for that and will do the clearing when the memory is coming from the glibc stock and not the kernel. But even in that case it's only doing clearing when the page is already in the process address space. So a process will always receive zero pages from the kernel, but the malloc() implementation is made more efficient by giving you back some of your own free()'d memory that from the kernel's point of view was never given back.
Does that sound about right?
From the glibc side I believe you are exactly correct.
OK, it's not guaranteed that it will be, but the source shows several code paths where memset can be called during calloc():-
http://sourceware.org/git/?p=glibc.git;a=blob_plain;f=malloc...
My quick experiement with 32-bit libc-2.13 showed that using calloc() is significantly slower than using malloc().
[EDIT] Should have read pedrocr's response fully.
Interestingly, in glibc-2.15, the code for calloc (well, public_cALLOc) is longer than that for malloc. Most of that actually seems just to be doing magic to figure out when it actually needs to clear it. So in any cases where calloc is touching reused memory, it clears that itself. Otherwise, things end up at either mmapping MAP_ANONYMOUS or sbrking, which simply allocates pages that all get cleared on access (well, on write) anyway for security reasons.
Honestly I was surprised how much indirection and optimization there was. I knew that there were some clever things being done and they try to take advantage of processor features. But this stuff really does everything possible to avoid even a single unnecessary cycle. I'm impressed.
So in the general case, calloc might do some extra work. But where you're just callocing heaps and heaps (tee hee) it's not likely to. Strange, I could have sworn I just stumbled upon a case where someone claimed doing that was noticeably slower, but now I can't find it... was going to be very curious how that was the case. But after this romp I'm tired.
Yet, I have now been tricked into seeing it twice, as in addition to being on the HN home page for over 6 hours (with not that many upvotes, but still way too many) it was renamed by a moderator from the original title it was posted with ("Malloc never fails", weirdly in the opposite direction of the policy of "use the original title" that is normally cited for legitimizing renames) so you couldn't recognize "oh, this is that wrong article from earlier".
Worse, a somewhat informative comment on this site from the user "khm", one that links to a better article that discusses these issues with the right terminology an in context with the OOM killer, is marked [dead], caught by some spam filter or maybe even dowvoted/flagged to death by readers.
Frowny pants.
In result a Xen system with 128mb RAM can run much more than a VZ with 512MB.