4 ms·

For memory allocation you often don't need to use malloc. Many (most?) programs can mmap a large region of memory and allocate from that. Then when you're done

For memory allocation you often don't need to use malloc. Many (most?) programs can mmap a large region of memory and allocate from that. Then when you're done you just unmap the region. This is much easier to use since you only have to remember to unmap once as opposed to handling each allocated pointer individually. Edit: Here is a paper that touches a bit on what I'm describing: http://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf http://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf Also, to clarify, I'm not saying allocate yourself a big piece of memory and then reimplement malloc on top of that. You literally just get a big piece of memory and every time you want to allocate something new from it add the offset to the base address, return that to the user, and store the new offset.

deleted 11y ago
[deleted]
rc4algorithm 11y ago
No no no no no. When you do this, you are: 1) Reinventing malloc for no good reason 2) Opening yourself up to a whole world of security holes See Bob Beck's talk on the first 30 days of LibreSSL. Heartbleed wouldn't have been nearly as catastrophic if OpenSSL just used the system memory allocator like normal people.
- jeffreyrogers 11y ago
  I don't understand how this could lead to a security hole any more easily than using malloc could. Can you give an example? The system memory allocator is using mmap internally anyways (on Linux and anywhere else using the Doug Lea allocator at least) and a simple region based allocator is only a couple dozen lines of code. The semantics are simple as well: region create_region(size_t size); void * allocate(region *r, size_t size); void destroy_region(region *r); Edit: also, you're not reinventing malloc for no good reason. A region based allocator is much faster, possibly at the expense of using more space than the system allocator (because you might reserve more space than you actually need).
  - SamReidHughes 11y ago
    If you want to count examples you're reasoning about this the wrong way. The question is what way leads to a higher probability of making a mistake, not the existence of discrete examples. Considering that one way, Valgrind works out of the box, but with your way, it doesn't, I think the answer to that question is quite clear. Even if there weren't tools like that, it is easier to read code and understand pointers' lifetimes when they're being handled individually, instead of having their lifetimes be part of some far-off region.
    - jeffreyrogers 11y ago
      The whole point of using regions is not to be worrying about pointer lifetimes. And you don't need Valgrind when you have regions since you aren't going to leak memory by forgetting to free something. Valgrind solves a problem that doesn't exist when you use regions. If you're really worried that you'll leak an entire region worth of data just allocate the region with malloc instead of mmap and then use Valgrind to tell you what regions you aren't destroying.
      - SamReidHughes 11y ago
        Valgrind isn't for memory leaks, its main purpose is for catching out-of-bounds and uninitialized accesses.
  - adrusi 11y ago
    The point is that when you use malloc, an attacker exploiting a buffer overrun can't easily guess at the offset they need to find useful data. When you allocate everything in a big region, your process can be expected to read past the object bounds, so an attacker might be able to probe the address space (also the memory layout might be more deterministic). If they try to probe like that in a program that allocates with malloc, they'll just segfault the program.
    - jeffreyrogers 11y ago
      Yes, this is a reasonable objection.
- nitrogen 11y ago
  There are a few good reasons to reimplement malloc(), but of course it needs to be done very very carefully. For example, with a naive buddy list allocator it is (or was, in 2007) possible to more than triple allocation throughput vs. malloc(), but one loses many of malloc()'s security features.
caf 11y ago
Setting aside the wisdom of this approach, if you were going to do this why wouldn't you just use malloc() to allocate the single large arena that you're going to allocate from yourself? It's still just one free(). In other words, the malloc-versus-mmap distinction here isn't the important one, it's the custom allocator versus system allocator one.
- jeffreyrogers 11y ago
  That would work too. malloc() uses mmap() internally for large allocations, so the reason to use mmap() is just to skip all the other stuff malloc() does (which you don't care about if you have a custom allocator).
userbinator 11y ago
For memory allocation you often don't need to use malloc. True. Many (most?) programs can mmap a large region of memory and allocate from that. You don't even need to do that for many applications. Coming from an embedded systems background where dynamic allocation is highly discouraged and almost never necessary, the amount of superfluous allocation/deallocation I see in a lot of code is astounding; maybe it's because of my experience, but I can often very easily find a way to do something without dynamic allocation and consequently O(n) space, with what usually turns out to be simpler (thus less chance of being buggy) code and O(1) space. But when you do need dynamic allocation, malloc() isn't bad at all.
- jeffreyrogers 11y ago
  This is a very good point.
btrask 11y ago
Hey Jeff, I had to double check because I couldn't believe this was you. I'm a big fan of the Jeff and Casey Show! The problem with doing custom allocation is not specifically due to bugs in the allocator per se, but because your custom allocator will probably not be hardened against other bugs like some other allocators are. Specifically you will piss off the OpenBSD people who have put a lot of work into their allocator with "exploit mitigations." A bump allocator is pretty much guaranteed to let overflows (reads and writes) touch other valid memory. A hardened allocator will use guard pages and other tricks to prevent those bugs from being exploitable. One thing you can do is use bump allocators within "security zones." For example data related to a single user can be allocated together without much risk, but data from separate users is kept separate. This is very different from the world of game programming. I've been wondering lately if there will be some sort of bifurcation of the field.
- jeffreyrogers 11y ago
  Ahhh, this makes a lot of sense. Also, I think you're mixing me up with Jeff Roberts. I'm Jeff Rogers :). But yes, the Jeff and Casey Show is awesome :).
  - btrask 11y ago
    Oh darn!

deleted 11y ago

[deleted]

rc4algorithm 11y ago

No no no no no. When you do this, you are: 1) Reinventing malloc for no good reason 2) Opening yourself up to a whole world of security holes See Bob Beck's talk on the first 30 days of LibreSSL. Heartbleed wouldn't have been nearly as catastrophic if OpenSSL just used the system memory allocator like normal people.

jeffreyrogers 11y ago
I don't understand how this could lead to a security hole any more easily than using malloc could. Can you give an example? The system memory allocator is using mmap internally anyways (on Linux and anywhere else using the Doug Lea allocator at least) and a simple region based allocator is only a couple dozen lines of code. The semantics are simple as well: region create_region(size_t size); void * allocate(region *r, size_t size); void destroy_region(region *r); Edit: also, you're not reinventing malloc for no good reason. A region based allocator is much faster, possibly at the expense of using more space than the system allocator (because you might reserve more space than you actually need).
- SamReidHughes 11y ago
  If you want to count examples you're reasoning about this the wrong way. The question is what way leads to a higher probability of making a mistake, not the existence of discrete examples. Considering that one way, Valgrind works out of the box, but with your way, it doesn't, I think the answer to that question is quite clear. Even if there weren't tools like that, it is easier to read code and understand pointers' lifetimes when they're being handled individually, instead of having their lifetimes be part of some far-off region.
  - jeffreyrogers 11y ago
    The whole point of using regions is not to be worrying about pointer lifetimes. And you don't need Valgrind when you have regions since you aren't going to leak memory by forgetting to free something. Valgrind solves a problem that doesn't exist when you use regions. If you're really worried that you'll leak an entire region worth of data just allocate the region with malloc instead of mmap and then use Valgrind to tell you what regions you aren't destroying.
    - SamReidHughes 11y ago
      Valgrind isn't for memory leaks, its main purpose is for catching out-of-bounds and uninitialized accesses.
- adrusi 11y ago
  The point is that when you use malloc, an attacker exploiting a buffer overrun can't easily guess at the offset they need to find useful data. When you allocate everything in a big region, your process can be expected to read past the object bounds, so an attacker might be able to probe the address space (also the memory layout might be more deterministic). If they try to probe like that in a program that allocates with malloc, they'll just segfault the program.
  - jeffreyrogers 11y ago
    Yes, this is a reasonable objection.
nitrogen 11y ago
There are a few good reasons to reimplement malloc(), but of course it needs to be done very very carefully. For example, with a naive buddy list allocator it is (or was, in 2007) possible to more than triple allocation throughput vs. malloc(), but one loses many of malloc()'s security features.

caf 11y ago

Setting aside the wisdom of this approach, if you were going to do this why wouldn't you just use malloc() to allocate the single large arena that you're going to allocate from yourself? It's still just one free(). In other words, the malloc-versus-mmap distinction here isn't the important one, it's the custom allocator versus system allocator one.

jeffreyrogers 11y ago
That would work too. malloc() uses mmap() internally for large allocations, so the reason to use mmap() is just to skip all the other stuff malloc() does (which you don't care about if you have a custom allocator).

userbinator 11y ago

For memory allocation you often don't need to use malloc. True. Many (most?) programs can mmap a large region of memory and allocate from that. You don't even need to do that for many applications. Coming from an embedded systems background where dynamic allocation is highly discouraged and almost never necessary, the amount of superfluous allocation/deallocation I see in a lot of code is astounding; maybe it's because of my experience, but I can often very easily find a way to do something without dynamic allocation and consequently O(n) space, with what usually turns out to be simpler (thus less chance of being buggy) code and O(1) space. But when you do need dynamic allocation, malloc() isn't bad at all.

jeffreyrogers 11y ago
This is a very good point.

btrask 11y ago

Hey Jeff, I had to double check because I couldn't believe this was you. I'm a big fan of the Jeff and Casey Show! The problem with doing custom allocation is not specifically due to bugs in the allocator per se, but because your custom allocator will probably not be hardened against other bugs like some other allocators are. Specifically you will piss off the OpenBSD people who have put a lot of work into their allocator with "exploit mitigations." A bump allocator is pretty much guaranteed to let overflows (reads and writes) touch other valid memory. A hardened allocator will use guard pages and other tricks to prevent those bugs from being exploitable. One thing you can do is use bump allocators within "security zones." For example data related to a single user can be allocated together without much risk, but data from separate users is kept separate. This is very different from the world of game programming. I've been wondering lately if there will be some sort of bifurcation of the field.

jeffreyrogers 11y ago
Ahhh, this makes a lot of sense. Also, I think you're mixing me up with Jeff Roberts. I'm Jeff Rogers :). But yes, the Jeff and Casey Show is awesome :).
- btrask 11y ago
  Oh darn!