5 ms·

A Story Of realloc (And Laziness)

130 points by janerik 12y ago

CJefferson 12y ago
I have also found people often unestimate realloc (but have never done the same level of investigation to find out just how clever it is!) 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.
- plorkyeran 12y ago
  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.
  - nroets 12y ago
    Are you saying that vector<char> with 'grow()' is substantially slower than the given C macro ? By how much ?
    - plorkyeran 12y ago
      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.
      - BugBrother 12y ago
        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.
        plorkyeran 12y ago
        std::vector guarantees that it stores its elements contiguously, as this is required for a lot of use-cases (such as passing the buffer to one of the millions of functions that take just a pointer and a size).
        stormbrew 12y ago
        > 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/ 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.
  - bodyfour 12y ago
    jemalloc's non-standard interface gives you some of what you want, expectially xallocx() http://www.canonware.com/download/jemalloc/jemalloc-latest/doc/jemalloc.html http://www.canonware.com/download/jemalloc/jemalloc-latest/d... 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 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/n3536.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n353...
    - plorkyeran 12y ago
      Folly does take advantage of jemalloc to expand allocations in-place when possible, but afaik it doesn't do the more extreme optimization mentioned in the article where pages are moved to a different virtual address without actually paging into memory. Sized deallocation made it into C++14.
      - bodyfour 12y ago
        Since 2.1, jemalloc does support using mremap to do large realloc()'s, although it seems to be off by default. You need "./configure --enable-mremap" to get it. That's good news about sized deallocation, I hadn't noticed that there is an updated "N3778" proposal which apparently was accepted. I still haven't seen the dlmalloc work to support that show up in the main svn branch.
kabdib 12y ago
I fixed a crippling bug on another platform that was taking down whole servers, because someone was depending on a clever realloc to behave well. This is implementation coupling at its worst. Don't do it.
- xroche 12y ago
  Yes and no. The real error here would be to realloc without any geometric progression IMHO - ie. reallocating one more byte each time, which would behave well on Linux (except the libc call cost of course) but not on other implementations (such as some Microsoft's MSVCRT versions). Assuming realloc has no catastrophic performance impact is not something too daring.
asveikau 12y ago
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.
- rfrey 12y ago
  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?
  - asveikau 12y ago
    > how frequent is memory allocation failure nowadays 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.
  - fprawn 12y ago
    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 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.
ctz 12y ago
The realloc implementation in this blog is incorrect: the passed in pointer must not be freed if realloc is called with a non-zero length and returns NULL. This will cause a double free in correct callers. 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.
- xroche 12y ago
  I fixed the double free. I must admit that the code was typed as I wrote the blog entry, and is horribly wrong :)
optimiz3 12y ago
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.
- greenyoda 12y ago
  "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 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.
  - ANTSANTS 12y ago
    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.
- xroche 12y ago
  Yes, indeed - but the code was not meant to be an actual implementation, just a (bad) minimalistic example.
crackerz 12y ago
And this is why OpenSource is awesome.
- __david__ 12y ago
  Agreed. Not sure why people are downvoting you. It blows my mind every time I think, "I wonder how <some program> works?" and I'm able to just "apt-get source some_program" and check it out. 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.
picomancer 12y ago
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...
- nhaehnle 12y ago
  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.
  - whoopdedo 12y ago
    What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious. 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?
    - nhaehnle 12y ago
      Do I even have the promise that malloc will return unfragmented memory? What do you mean by this? malloc returns memory that is contiguous in the virtual address space. It may not be contiguous in the physical address space, but that should be irrelevant for cache behavior. Will I be thrashing the cache if I use realloc frequently? I suppose. But if you use realloc, you should anyway ensure that you realloc geometrically growing chunks of memory (e.g., whenever you need a new buffer, you multiply its size by a constant factor like 1.2 instead of just adding an element at a time). As a result, realloc() should be infrequent enough that it normally doesn't matter.
mjcohen 12y ago
In the original #define, the parameter is lower case "c" and the expansion uses upper case "C".
greatsuccess 12y ago
Pretty sad that I needed to read through 20 minutes of code when he could have just said "It reallocs the paging table" What do you think we are a bunch of fucking idiots? Must be nice to be 22 and think you have educational value.

130 points by janerik 12y ago

I have also found people often unestimate realloc (but have never done the same level of investigation to find out just how clever it is!) 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.

plorkyeran 12y ago
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.
- nroets 12y ago
  Are you saying that vector<char> with 'grow()' is substantially slower than the given C macro ? By how much ?
  - plorkyeran 12y ago
    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.
    - BugBrother 12y ago
      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.
      - plorkyeran 12y ago
        std::vector guarantees that it stores its elements contiguously, as this is required for a lot of use-cases (such as passing the buffer to one of the millions of functions that take just a pointer and a size).
      - stormbrew 12y ago
        > 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/ 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.
- bodyfour 12y ago
  jemalloc's non-standard interface gives you some of what you want, expectially xallocx() http://www.canonware.com/download/jemalloc/jemalloc-latest/doc/jemalloc.html http://www.canonware.com/download/jemalloc/jemalloc-latest/d... 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 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/n3536.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n353...
  - plorkyeran 12y ago
    Folly does take advantage of jemalloc to expand allocations in-place when possible, but afaik it doesn't do the more extreme optimization mentioned in the article where pages are moved to a different virtual address without actually paging into memory. Sized deallocation made it into C++14.
    - bodyfour 12y ago
      Since 2.1, jemalloc does support using mremap to do large realloc()'s, although it seems to be off by default. You need "./configure --enable-mremap" to get it. That's good news about sized deallocation, I hadn't noticed that there is an updated "N3778" proposal which apparently was accepted. I still haven't seen the dlmalloc work to support that show up in the main svn branch.

kabdib 12y ago

I fixed a crippling bug on another platform that was taking down whole servers, because someone was depending on a clever realloc to behave well. This is implementation coupling at its worst. Don't do it.

xroche 12y ago
Yes and no. The real error here would be to realloc without any geometric progression IMHO - ie. reallocating one more byte each time, which would behave well on Linux (except the libc call cost of course) but not on other implementations (such as some Microsoft's MSVCRT versions). Assuming realloc has no catastrophic performance impact is not something too daring.

asveikau 12y ago

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.

rfrey 12y ago
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?
- asveikau 12y ago
  > how frequent is memory allocation failure nowadays 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.
- fprawn 12y ago
  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 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.

ctz 12y ago

The realloc implementation in this blog is incorrect: the passed in pointer must not be freed if realloc is called with a non-zero length and returns NULL. This will cause a double free in correct callers. 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.

xroche 12y ago
I fixed the double free. I must admit that the code was typed as I wrote the blog entry, and is horribly wrong :)

optimiz3 12y ago

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.

greenyoda 12y ago
"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 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.
- ANTSANTS 12y ago
  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.
xroche 12y ago
Yes, indeed - but the code was not meant to be an actual implementation, just a (bad) minimalistic example.

crackerz 12y ago

And this is why OpenSource is awesome.

__david__ 12y ago
Agreed. Not sure why people are downvoting you. It blows my mind every time I think, "I wonder how <some program> works?" and I'm able to just "apt-get source some_program" and check it out. 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.

picomancer 12y ago

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...

nhaehnle 12y ago
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.
- whoopdedo 12y ago
  What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious. 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?
  - nhaehnle 12y ago
    Do I even have the promise that malloc will return unfragmented memory? What do you mean by this? malloc returns memory that is contiguous in the virtual address space. It may not be contiguous in the physical address space, but that should be irrelevant for cache behavior. Will I be thrashing the cache if I use realloc frequently? I suppose. But if you use realloc, you should anyway ensure that you realloc geometrically growing chunks of memory (e.g., whenever you need a new buffer, you multiply its size by a constant factor like 1.2 instead of just adding an element at a time). As a result, realloc() should be infrequent enough that it normally doesn't matter.

mjcohen 12y ago

In the original #define, the parameter is lower case "c" and the expansion uses upper case "C".

greatsuccess 12y ago

Pretty sad that I needed to read through 20 minutes of code when he could have just said "It reallocs the paging table" What do you think we are a bunch of fucking idiots? Must be nice to be 22 and think you have educational value.