A Story Of realloc (And Laziness) • Hacker News Board

Re: A Story Of realloc (And Laziness)

#11

Post by joosters » Sun, Apr 06, 2014, 5:15 PM UTC

rfrey wrote: post #6

asveikau wrote: post #5

This bothers me so much: buffer = realloc(buffer, capa); Yeah, 'cause when it fails we didn't need the old buffer anyway... Might as well leak it.

Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?

Most Linux distributions run using an optimistic memory allocation system, whereby memory (RAM plus swap space) can be over-allocated. On these systems, your program can die due to lack of memory at any point in time. I.e. Even if you test the return values of every malloc() call, you still won't be safe.

Re: A Story Of realloc (And Laziness)

#12

Post by optimiz3 » Sun, Apr 06, 2014, 5:16 PM UTC

Code in the article for realloc is dangerous and wrong:

  void *realloc(void *ptr, size_t size) {
    void *nptr = malloc(size);
    if (nptr == NULL) {
      free(ptr);
      return NULL;
    }
    memcpy(nptr, ptr, size); // KABOOM
    free(ptr);
    return nptr;
  }

Line marked KABOOM copies $DEST_BYTE_COUNT, rather than $SOURCE_BYTE_COUNT.

Say you want to realloc a 1 byte buffer to a 4 byte buffer - you just copied 4 bytes from a 1 byte buffer which means you're reading 3 bytes from 0xDEADBEEF/0xBADF000D/segfault land.

EDIT: Also, this is why the ENTIRE PREMISE of implementing your own reallocator speced to just the realloc prototype doesn't make much sense. You simply don't know the size of the original data with just a C heap pointer as this is not standardized AFAIK.

Re: A Story Of realloc (And Laziness)

#13

Post by plorkyeran » Sun, Apr 06, 2014, 5:17 PM UTC

nroets wrote: post #8

plorkyeran wrote: post #4

Earlier quoted context omitted.

C++ really wants a realloc variant that extends an allocation if it can be extended without a copy, and leaves the allocation unchanged if it can't. The annoying thing is that there's no good reason why this can't exist beyond that the STL allocator interface happens not to have it.

Are you saying that vector with 'grow()' is substantially slower than the given C macro ? By how much ?

It always calls (the equivalent of) malloc + memcpy + free for each grow, so it can be anywhere from the exact same speed (when realloc does the same thing internally) to absurdly slower (in the given case of a large array that has to be paged in). The first case is by far the most common case, but it is something that sometimes matters.

Re: A Story Of realloc (And Laziness)

#14

Post by twic » Sun, Apr 06, 2014, 5:30 PM UTC

rfrey wrote: post #6

asveikau wrote: post #5

This bothers me so much: buffer = realloc(buffer, capa); Yeah, 'cause when it fails we didn't need the old buffer anyway... Might as well leak it.

Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?

On Linux, somewhat infamously, malloc never fails. It will always return a pointer to some fresh part of the address space. It is able to do this because, in turn, sbrk/anonymous mmap never fails - it always allocates some fresh address space. It is able to do this because Linux does not allocate physical memory (or swap) when it assigns address space, but when that address space is actually used. It will happily allocate more address space than it has memory for - a practice known as 'overcommit'. So, on Linux, you can indeed not worry about malloc failing:

http://www.scvalex.net/posts/6/ http://www.drdobbs.com/embedded-systems/malloc-madness/23160...

There are a few caveats to this.

Firstly, malloc actually can fail, not because it runs out of memory, but because it runs out of address space. If have 2^64 bytes of memory in your address space already (2^48 on most practical machines, i believe), then there is no value malloc could return that would satisfy you.

Secondly, this behaviour is configurable. An administrator could configure a Linux system not to do this, and instead to only allocate address space that can be backed with memory. And actually, some things i have read suggest that overcommit is not unlimited to begin with; the kernel will only allocate address space equal to some multiple of the memory it has.

Thirdly, failure is conserved. While malloc can't fail, something else can. Linux's behaviour is essentially fractional reserve banking with address space, and that means that the allocator will sometimes write cheques the page tables can't cash. If it does, if it allocates more address space than it can supply, and if every process attempts to use all the address space that it has been allocated, we have the equivalent of a run on the bank, and there is going to be a failure. The way the failure manifests is through the action of the out-of-memory killer, which picks one process on the system, kills it, and so reclaims the memory allocated to it for distribution to surviving processes:

http://linux-mm.org/OOM_Killer

The OOM killer is a widely-feared bogeyman amongst Linux sysadmins. It sometimes manages to choose exactly the wrong thing as a victim. At one time, and perhaps still, it had a particular grudge against PostgreSQL:

http://thoughts.davisjeff.com/2009/11/29/linux-oom-killer/

And in the last month or so, on systems where i work, i have seen a situation where a Puppet run on an application server provoked the OOM killer into killing the application, and another where a screwed up attempt to create a swap file on an infrastructure server provoked it into killing the SSH daemon and BIND.

I don't know about what other operating systems do. Apparently all modern unixes overcommit address space in much the same way as Linux. However, i can't believe that FreeBSD handles this as crassly as Linux does.

Re: A Story Of realloc (And Laziness)

#15

Post by smtddr » Sun, Apr 06, 2014, 5:33 PM UTC

joosters wrote: post #11

rfrey wrote: post #6

Earlier quoted context omitted.

Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?

Most Linux distributions run using an optimistic memory allocation system, whereby memory (RAM plus swap space) can be over-allocated. On these systems, your program can die due to lack of memory at any point in time. I.e. Even if you test the return values of every malloc() call, you still won't be safe.

I did not believe you, but then I did "man malloc" and sure enough, in the NOTES section at the bottom.

>>By default, Linux follows an optimistic memory allocation strategy. This means that when malloc() returns non-NULL there is no guarantee that the memory really is available.

So it's like airlines overbooking seats; the system just hopes that the memory is available when you actually try to use it. I had no idea. That would be an extremely annoying bug to try and track down. How would one even do it? Is there a way to test if you truly have the memory without segfaulting?

Re: A Story Of realloc (And Laziness)

#16

Post by comex » Sun, Apr 06, 2014, 5:43 PM UTC

smtddr wrote: post #15

joosters wrote: post #11

Earlier quoted context omitted.

Most Linux distributions run using an optimistic memory allocation system, whereby memory (RAM plus swap space) can be over-allocated. On these systems, your program can die due to lack of memory at any point in time. I.e. Even if you test the return values of every malloc() call, you still won't be safe.

I did not believe you, but then I did "man malloc" and sure enough, in the NOTES section at the bottom. >>By default, Linux follows an optimistic memory allocation strategy. This means that when malloc() returns non-NULL there is no guarantee that the memory really is available. So it's like airlines overbooking seats; the system just hopes that the memory is available when you actually try to use it. I had no idea.…

If the memory isn't available, it doesn't segfault; it blocks until memory is available, thanks to either swap or the OOM killer doing its thing.

If you want to ensure that you don't block, you can use mlock().

Re: A Story Of realloc (And Laziness)

#17

Post by asveikau » Sun, Apr 06, 2014, 5:50 PM UTC

twic wrote: post #14

rfrey wrote: post #6

Earlier quoted context omitted.

Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?

On Linux, somewhat infamously, malloc never fails. It will always return a pointer to some fresh part of the address space. It is able to do this because, in turn, sbrk/anonymous mmap never fails - it always allocates some fresh address space. It is able to do this because Linux does not allocate physical memory (or swap) when it assigns address space, but when that address space is actually used. It will happily all…

> On Linux, somewhat infamously, malloc never fails.

Pretty close to true but I think that is a bit of a simplification. I seem to recall for instance on 32-bit Linux it's not hard to get malloc to return NULL: ask for some absurd size, like maybe a few allocations of a gigabyte or two, something that fits in a size_t but a 32-bit address space could not possibly accommodate with all the other things in the address space (stacks, your binary, libraries, kernel-only addresses in the page table, etc).

Re: A Story Of realloc (And Laziness)

#18

Post by smtddr » Sun, Apr 06, 2014, 5:56 PM UTC

comex wrote: post #16

smtddr wrote: post #15

Earlier quoted context omitted.

I did not believe you, but then I did "man malloc" and sure enough, in the NOTES section at the bottom. >>By default, Linux follows an optimistic memory allocation strategy. This means that when malloc() returns non-NULL there is no guarantee that the memory really is available. So it's like airlines overbooking seats; the system just hopes that the memory is available when you actually try to use it. I had no idea.…

If the memory isn't available, it doesn't segfault; it blocks until memory is available, thanks to either swap or the OOM killer doing its thing. If you want to ensure that you don't block, you can use mlock().

Well that's even more interesting! So you can have a program appear to be stuck and not know why! At least now I know I can use mlock() everywhere to determine if it locked on a write to promised-but-not-yet-available memory.

Re: A Story Of realloc (And Laziness)

#19

Post by otterley » Sun, Apr 06, 2014, 6:07 PM UTC

twic wrote: post #14

rfrey wrote: post #6

Earlier quoted context omitted.

Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?

On Linux, somewhat infamously, malloc never fails. It will always return a pointer to some fresh part of the address space. It is able to do this because, in turn, sbrk/anonymous mmap never fails - it always allocates some fresh address space. It is able to do this because Linux does not allocate physical memory (or swap) when it assigns address space, but when that address space is actually used. It will happily all…

> On Linux, somewhat infamously, malloc never fails. It will always return a pointer to some fresh part of the address space. It is able to do this because, in turn, sbrk/anonymous mmap never fails - it always allocates some fresh address space. It is able to do this because Linux does not allocate physical memory (or swap) when it assigns address space, but when that address space is actually used. It will happily allocate more address space than it has memory for - a practice known as 'overcommit'. So, on Linux, you can indeed not worry about malloc failing

True. However, you can disable this behavior if you like by running 'sysctl vm.overcommit_memory=2'; see proc(5).

Re: A Story Of realloc (And Laziness)

#20

Post by srean » Sun, Apr 06, 2014, 6:09 PM UTC

rfrey wrote: post #6

asveikau wrote: post #5

This bothers me so much: buffer = realloc(buffer, capa); Yeah, 'cause when it fails we didn't need the old buffer anyway... Might as well leak it.

Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?

Failure or not, this is the highway to shitty software with bad user experience (except for very special cases where it makes sense).

For me the funniest part has been that the people who seem entitled to write sloppy software are the exact same set who would have the shrillest voices complaining that firefox is so slow and bloated (although its not anymore)

Many believe that its OK to hog memory, that it is an infinite resource. Many believe it is OK to be slow as long as it meets specs. Many believe your user application is the only application that the user will be running at any point in time. However, when your competition does it leaner and faster, you (not you personally, a generic software) are mostly going to be toast.