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.
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 a pointer to (block_address + N) to the user. When you then want to realloc() a block, just look in the block header (N bytes before the user's pointer) for the size.
The block header can store other useful stuff, like debugging information. I once implemented a memory manager for debugging that could generate a list of all leaked blocks at the end of the program with the file names and line numbers where they were allocated.
"If the space cannot be allocated, the object [*ptr] shall remain unchanged."On several occasions I have wanted to use mmap, mremap, and friends more often to do fancy things like copy-on-write memory. However, I always find this whole area depressingly poorly documented, and hard to do (because if you mess up a copy-on-write call, it just turns into a copy it seems, with the same result but less performance).
While it's good realloc is clever, I find it increasingly embarassing how badly C (and even worse, C++ which doesn't even really have realloc (as most C++ types can't be bitwise moved) memory allocation maps to what operating systems efficiently support.
There have been C++ templates written that use jemalloc-specific calls; for instance see Folly from facebook. I haven't taken a close look, but I know they do some jemalloc-specific code: https://github.com/facebook/folly/tree/master/folly
The other allocated-related thing that C++ really wants (and could benefit C as well) is "sized deallocation". Most of the time you often know the exact size of the memory you allocated. If you could pass that to free() the allocator could save some work determining it. In the case of C++ the compiler can often do this on your behalf for many "delete" calls (at least in the cases where it knows the exact type). Google did an implementation of this idea and got good results. They submitted a proposal to the standards body but I don't know if there is any recent activity. I hope it does happen though: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n353...
buffer = realloc(buffer, capa);
Yeah, 'cause when it fails we didn't need the old buffer anyway... Might as well leak it.Wrong? Are there lots of ways allocation can fail besides low memory conditions?
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.
I'd guess that it varies a lot by domain and project but from what I've seen, pretty common.
> I'd think that if allocs began to fail, there was no recovery anyhow
I think this is what both high-level languages and the Linux "over-commit-by-default" policy have convinced people is the normal behavior. However in my experience it's not that hard to make OOM simply bubble up the stack and have all the callers up the stack free their resources, then let the rest of the program keep running. It doesn't have to be a catastrophic event. You just have to be consistent about handling it, and write code expecting it.
> Are there lots of ways allocation can fail besides low memory conditions?
To think of a few, there's running out of memory, but there's also running out of address space. The latter is not so hard to accomplish on a 32-bit system. You could ask for a chunk of memory where, if you could coalesce all the free space throughout the heap, you may have enough space, but you can't make it into a contiguous allocation.
On Windows I've also seen the kernel run out of nonpaged pool, which is more space constrained than the rest of memory. I've seen this when a lot of I/O is going on. You get things like WriteFile failing with ERROR_NOT_ENOUGH_MEMORY.
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.
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 better, the best practice is still to not check the return from allocators. Running out of memory in a program intended for an embedded platform should be considered a bug.
As someone else pointed out, the example call of realloc is also incorrect.
edit: also, malloc is incorrect for three reasons: 1) sbrk doesn't return NULL on failure, 2) a large size_t length will cause a contraction in the heap segment rather than an allocation, and 3) sbrk doesn't return a pointer aligned in any particular way, whereas malloc must return a pointer suitably aligned for all types.
This is implementation coupling at its worst. Don't do it.
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...
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.
But what does this mean for locality? Will I be thrashing the cache if I use realloc frequently? Do I even have the promise that malloc will return unfragmented memory?
Working with Linux and having the source (and the ability to change it) for entire stack all the way down to and including the kernel is liberating. As a programmer it feels like the entire world is open to me.
I guess that's GNU's dream brought to life, really.