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

Re: A Story Of realloc (And Laziness)

#31

Post by pjmlp » Sun, Apr 06, 2014, 7:51 PM UTC

fprawn wrote: post #10

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?

Memory allocation failures are virtually non-existent in modern desktop computers. Good practice is to not test return values from malloc, new, etc. Memory can be allocated beyond RAM size, so by the time a failure occurs your program really should crash and return its resources. Embedded systems have fewer resources and some will not have virtual memory and so the situation will be different. But unless you know bet…

That is the open path to security exploits.

Re: A Story Of realloc (And Laziness)

#32

Post by fprawn » Sun, Apr 06, 2014, 8:16 PM UTC

fprawn wrote: post #10

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?

Memory allocation failures are virtually non-existent in modern desktop computers. Good practice is to not test return values from malloc, new, etc. Memory can be allocated beyond RAM size, so by the time a failure occurs your program really should crash and return its resources. Embedded systems have fewer resources and some will not have virtual memory and so the situation will be different. But unless you know bet…

I'll clarify this. I'm not saying you shouldn't ever check return values, that's obviously not the right thing to do. And of course there are exceptions to the general rule. If you're allocating a large chunk of memory and there's a reasonable expectation that it could fail, that should be reported, of course.

In the general case, however, if allocating 100 bytes fails, reporting that error is also likely to fail. An actual memory allocation failure on a modern computer running a modern OS is a very rare and very bad situation. It's rarely recoverable.

It's not bad to handle allocation failures, but in the vast majority of cases it's very unreasonable to do so. You can write code for it if you want, have fun.

And just to be completely clear, I am ONLY talking about calls to malloc, new, realloc, etc. NOT to OS pools or anything like that. Obviously, if you allocate a 4Mb buffer for something (or the OS does for you), you expect that you might run out. This is ONLY in regards to calls to lower level heap allocators.

I don't think you'll find any experienced programmer recommending that you always check the return from malloc. That's completely absurd. There are always exceptions to the rule, however.

Re: A Story Of realloc (And Laziness)

#33

Post by htns » Sun, Apr 06, 2014, 8:40 PM UTC

yaur wrote: post #27

fprawn wrote: post #10

Earlier quoted context omitted.

Memory allocation failures are virtually non-existent in modern desktop computers. Good practice is to not test return values from malloc, new, etc. Memory can be allocated beyond RAM size, so by the time a failure occurs your program really should crash and return its resources. Embedded systems have fewer resources and some will not have virtual memory and so the situation will be different. But unless you know bet…

Ugh. I would much rather know that the process died because of allocation failure than try to figure out why some code is trying to write to a random null pointer as these are two very different types of bugs.

I'm having a hard time picturing a situation where it would be tough to figure out. Typically you allocate memory to use it right after. errno will be set too.

Of course, there is no reason to not do all your allocation through a wrapper function which does check and abort on failure. I think the point was that surviving malloc failures is a dubious approach - instead go all in, or if it's a long-running service, provide a configurable max memory cap and assume that much will be available.

Re: A Story Of realloc (And Laziness)

#34

Post by picomancer » Sun, Apr 06, 2014, 8:45 PM UTC

This is really neat. Somehow I always assumed realloc() copied stuff instead of using the page table.

But say you have 4K page table size. You malloc() in turn a 2K object, a 256K object, and another 2K object, ending up with 2K, 256K, 2K in memory. Then your 256K is not aligned on a page boundary. If you realloc() the 256K it has to move since it's surrounded by two objects. When you do that, you'll wind up with the two pages on the end being mapped to multiple addresses. Which is actually just fine...Interesting...

Re: A Story Of realloc (And Laziness)

#35

Post by yongjik » Sun, Apr 06, 2014, 9:05 PM UTC

plorkyeran wrote: post #13

nroets wrote: post #8

Earlier quoted context omitted.

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.

It seems that even vector::shrink_to_fit is implemented that way.

That is, when you call shrink_to_fit, it first copies all elements it has, swaps itself with the new copy, and deletes the original vector. (Probably because there's no portable way of returning only part of a contiguous memory region. Yikes.)

http://stackoverflow.com/questions/2695552/how-to-shrink-to-...

Re: A Story Of realloc (And Laziness)

#36

Post by nhaehnle » Sun, Apr 06, 2014, 9:06 PM UTC

picomancer wrote: post #34

This is really neat. Somehow I always assumed realloc() copied stuff instead of using the page table. But say you have 4K page table size. You malloc() in turn a 2K object, a 256K object, and another 2K object, ending up with 2K, 256K, 2K in memory. Then your 256K is not aligned on a page boundary. If you realloc() the 256K it has to move since it's surrounded by two objects. When you do that, you'll wind up with the…

The libc memory allocator does not simply hand out memory contiguously. In your example, the 256K block will end up being 4K aligned.

In fact, that's what the article already explains: the large alloc will just end up being passed through to the kernel, which only deals at page granularity.

Re: A Story Of realloc (And Laziness)

#37

Post by joosters » Sun, Apr 06, 2014, 9:22 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().

That's not quite true. The problem is more insidious that that.

Think of the memory requirements of the fork() system call. It clones the current process, making an entire copy of it. Sure, there's lots of copy-on-write optimisation going on, but if you want guaranteed, confirmed memory, you need to have a backing store for that new process. The child process has every right to adjust all of its process memory.

So if a 4GB process calls fork(), you will suddenly need to reserve 4GB of RAM or new swap space for it. Or if you can't allocate that, you will have to make the fork() fail.

This can be terrible for users, since most often a process is going to fork() and then exec() a very small program. And it seems nonsensical for fork() to fail with ENOMEM when it appears that there is lots of free memory left. But to ensure memory is strictly handled, that's what you have to do.

The alternative, which most distributions use, is to optimistically allocate memory. Let the fork() and other calls succeed. But you run the risk of the child process crashing at any point in the future when it touches its own 'confirmed' memory and the OS being unable to allocate space for it. So the memory failures are not discovered at system call points. There's no return code to spot the out of memory condition. The OS can't even freeze up until memory is available because there's no guarantee that memory will become available.

Re: A Story Of realloc (And Laziness)

#38

Post by joosters » Sun, Apr 06, 2014, 9:26 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.…

No. All you can do is try writing to it and see what happens (you can catch the segfault though).

http://opsmonkey.blogspot.co.uk/2007/01/linux-memory-overcom... has some more info.

Re: A Story Of realloc (And Laziness)

#39

Post by stormbrew » Sun, Apr 06, 2014, 9:34 PM UTC

BugBrother wrote: post #22

plorkyeran wrote: post #13

Earlier quoted context omitted.

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.

Huh, is it really implemented like that?! Why use realloc when growing an array you have an interface to? Just add another allocated buffer to the previous allocated areas. When there are too many small areas, consolidate with realloc/free. Much faster (yes yes, almost always). (Disclaimer: Last time I used C++ I had hair. :-) ) Edit: OK, thanks plorkyeran.

> Huh, is it really implemented like that?!

Well, there is no grow() method on std::vector, so ... no?

But generally speaking, std::vector implementations are basically required to[1] grow the backing store exponentially so that adding elements to them absolutely does not call malloc on every growth of the vector.

You can make a vector do this kind of pessimistic allocation by calling reserve() for every element you add, which will cause the allocation of exactly the amount you reserved. This would be dumb, though. Reserve is there so you can allocate a precise large number and avoid even the logarithmic cost of allocation in adding elements to the vector.

It's really worth noting that this is a better worst case than the worst case for realloc(), which is entirely entitled to reallocate and copy every single time you call it. You're pretty likely to implement the exact same algorithm as vector if you DIY because of this exact issue when performance is important.

I do agree, though, that it would be nice if there was a failable realloc in C++ (and C for that matter) as described above, where it simply returns NULL if there's no more room in the allocated space. What to do in that event should really be up to the caller, not a black box algorithm sensitive to all sorts of variables.

[1] Because push_back() has a requirement of having amortized constant complexity, which means that it would be non-conforming to have the entire array moved for every push. http://www.cplusplus.com/reference/vector/vector/push_back/

[N] However, std::basic_string allows linear complexity on its push_back, so that may be what the poster meant. I'm not aware of any widely used implementation that actually does it in worse than amortized constant, though.

Re: A Story Of realloc (And Laziness)

#40

Post by ANTSANTS » Sun, Apr 06, 2014, 9:54 PM UTC

greenyoda wrote: post #25

optimiz3 wrote: post #12

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

"Also, this is why the ENTIRE PREMISE of implementing your own reallocator speced to just the realloc prototype doesn't make much sense." If you're reimplementing realloc() it's pretty easy to know the size of the allocated regions - you just need to store the size somewhere when you allocate a block. One common method is to allocate N extra bytes of memory whenever you do malloc() to hold the block header and return…

That would require either replacing malloc as well, or programming to the hairy details of your system's libc (ie knowing how and where it lays out the buffer metadata). The point is not that either are impossible, but that you can't replace realloc without doing one or the other.