• Create Account

### #ActualCornstalks

Posted 15 January 2013 - 11:30 AM

SiCrane mentions some very good points. I'm going to dive a little deeper into the internals of memory management and try to explain why the above is such a big problem.

There are various strategies for managing allocated memory. The allocator is what actually allocates the memory and frees it when you call new/delete. One very common allocation strategy is to request memory from the operating system when more is needed, but when its freed, don't immediately hand it back to the operating system. Keep it around. Why? Well, chances are the programmer is going to allocate more memory some time soon. If you give it all back to the OS right now, you'll just have to request more form the OS soon anyway (and these can all be pretty slow operations), so if the allocator hangs onto it, when you request more memory the allocator has some already available to give you. Yay, increase in speed! (there are other practical reasons why, but this is a big one) (and of course, if the allocator has a ton of free memory it's holding onto, it might decide to hand some of it back to the OS, but still keep a "reserve" of free memory hanging around).

Now, as you allocate memory and free it, your memory becomes fragmented. If you looked at it as one continuous block of memory, you'd have free chunks and allocated chunks mixed all over. How does the allocator keep track of what's allocated and what's free? Remember, this is the allocator! It can't just ask some other allocator for memory and keep a nice std::vector<ptr> of free and allocated chunks of memory. It's a pain in the butt to do, but here's a common way it's done:

Linked lists. In memory. When you allocate memory, the allocator does something like this:

void* malloc(size_t bytes) // same idea for new/new[] (horribly simplified, though)
{
void* ptr = RequestBytesFromOperatingSystem(bytes + HEADER_SIZE);

return (char*)ptr + HEADER_SIZE; // skip the header and give return the usable block to the user
}

The allocator allocates an extra few bytes to keep a header for each block of memory. This header usually says how large the block is, if the block is free or allocated and in use, if the next block (at ptr + bytes + HEADER_SIZE) is free or allocated and in use, and if the previous block is free or allocated and in use. If the block is free, the allocator might use some of the space in the block to store pointers to the previous and next free blocks (maintaining a linked list).

So now let's take this idea for memory blocks, and what SiCrane said above, and document them to figure out how a block of memory might look to the allocator

/*
Potential structure of a memory block allocated by new (that is, this block is allocated and in use):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
Bit 1: 1 if next block is free, 0 if next block is allocated
Bit 0: 1 if this block is free, 0 if this block is allocated
Pointer into segment table (4 bytes) (also acts as padding to maintain 8-byte alignment, like many CPUs need)
Instead of wasting the padding, we'll store which segment into our segment table this block should be
inserted into when its freed (so we don't have compute it when we free it, yay speed!)
User data (N bytes)
This is the memory the programmer is actually able to use

Potential structure of a memory block allocated by new [] (that is, this block is allocated and in use):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
Bit 1: 1 if next block is free, 0 if next block is allocated
Bit 0: 1 if this block is free, 0 if this block is allocated
Number of elements (4 bytes) (also acts as padding to maintain 8-byte alignment, like many CPUs need)
Instead of wasting the padding, we'll use it to store the number of elements in this array
User data (N bytes)
This is the memory the programmer is actually able to use

Potential structure of a free block of memory (after it's been freed by delete or delete []):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
Bit 1: 1 if next block is free, 0 if next block is allocated
Bit 0: 1 if this block is free, 0 if this block is allocated
Pointer to the next free block (4 bytes)
This way we can maintain a linked list of free blocks
Block data (N bytes)
Junk
*/

There are various allocation strategies and memory block formats, but the above encapsulates some common practices and ideas shared by many allocators.

Now, when the allocator tries to free a block of memory, it's going to try to use the block's header (the first 4 bytes of the block), and the following 4 bytes (what those bytes represent depends on whether or not you called new or new [], and depending on whether you call delete or delete [] it will change how those bytes are interpreted). If you call the delete on memory you used new [], the allocator will think the 4 bytes after the header are a pointer into the segment table (which they're not; those 4 bytes represent the number of elements in the array), and boom, you've successfully corrupted your memory (or hopefully crashed). If you call delete [] on memory you used new, the allocator will think the 4 bytes after the header are the number of elements in the array (which they're not; those 4 bytes represent a pointer into the segment table), and boom, you've successfully corrupted your memory (or hopefully crashed).

If different block formats and allocation strategies are used, it's possible to completely destroy the allocator's linked list of free/allocated blocks by calling the wrong delete, and now you've got memory leaks, you're overwriting data and double allocating the same blocks of memory for different uses, etc. Bad, bad, bad mojo.

Mixing delete with new [] or delete [] with new is not safe! Yes, it's possible the allocator implements new as new [1] (which would be a valid way to do it), and delete as delete [], but banking on that idea is like playing Russian roulette (with a gun that has more than one round in it).

Writing a correct, proper, fast, and efficient allocator is very hard work and involves lots of tricks. The last thing you need as an allocator is someone screwing up your tricks and hacks by freeing memory wrong.

### #2Cornstalks

Posted 15 January 2013 - 11:28 AM

SiCrane mentions some very good points. I'm going to dive a little deeper into the internals of memory management and try to explain why the above is such a big problem.

There are various strategies for managing allocated memory. The allocator is what actually allocates the memory and frees it when you call new/delete. One very common allocation strategy is to request memory from the operating system when more is needed, but when its freed, don't immediately hand it back to the operating system. Keep it around. Why? Well, chances are the programmer is going to allocate more memory some time soon. If you give it all back to the OS right now, you'll just have to request more form the OS soon anyway (and these can all be pretty slow operations), so if the allocator hangs onto it, when you request more memory the allocator has some already available to give you. Yay, increase in speed! (there are other practical reasons why, but this is a big one)

Now, as you allocate memory and free it, your memory becomes fragmented. If you looked at it as one continuous block of memory, you'd have free chunks and allocated chunks mixed all over. How does the allocator keep track of what's allocated and what's free? Remember, this is the allocator! It can't just ask some other allocator for memory and keep a nice std::vector<ptr> of free and allocated chunks of memory. It's a pain in the butt to do, but here's a common way it's done:

Linked lists. In memory. When you allocate memory, the allocator does something like this:

void* malloc(size_t bytes) // same idea for new/new[] (horribly simplified, though)
{
void* ptr = RequestBytesFromOperatingSystem(bytes + HEADER_SIZE);

return (char*)ptr + HEADER_SIZE; // skip the header and give return the usable block to the user
}

The allocator allocates an extra few bytes to keep a header for each block of memory. This header usually says how large the block is, if the block is free or allocated and in use, if the next block (at ptr + bytes + HEADER_SIZE) is free or allocated and in use, and if the previous block is free or allocated and in use. If the block is free, the allocator might use some of the space in the block to store pointers to the previous and next free blocks (maintaining a linked list).

So now let's take this idea for memory blocks, and what SiCrane said above, and document them to figure out how a block of memory might look to the allocator

/*
Potential structure of a memory block allocated by new (that is, this block is allocated and in use):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
Bit 1: 1 if next block is free, 0 if next block is allocated
Bit 0: 1 if this block is free, 0 if this block is allocated
Pointer into segment table (4 bytes) (also acts as padding to maintain 8-byte alignment, like many CPUs need)
Instead of wasting the padding, we'll store which segment into our segment table this block should be
inserted into when its freed (so we don't have compute it when we free it, yay speed!)
User data (N bytes)
This is the memory the programmer is actually able to use

Potential structure of a memory block allocated by new [] (that is, this block is allocated and in use):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
Bit 1: 1 if next block is free, 0 if next block is allocated
Bit 0: 1 if this block is free, 0 if this block is allocated
Number of elements (4 bytes) (also acts as padding to maintain 8-byte alignment, like many CPUs need)
Instead of wasting the padding, we'll use it to store the number of elements in this array
User data (N bytes)
This is the memory the programmer is actually able to use

Potential structure of a free block of memory (after it's been freed by delete or delete []):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
Bit 1: 1 if next block is free, 0 if next block is allocated
Bit 0: 1 if this block is free, 0 if this block is allocated
Pointer to the next free block (4 bytes)
This way we can maintain a linked list of free blocks
Block data (N bytes)
Junk
*/

There are various allocation strategies and memory block formats, but the above encapsulates some common practices and ideas shared by many allocators.

Now, when the allocator tries to free a block of memory, it's going to try to use the block's header (the first 4 bytes of the block), and the following 4 bytes (what those bytes represent depends on whether or not you called new or new [], and depending on whether you call delete or delete [] it will change how those bytes are interpreted). If you call the delete on memory you used new [], the allocator will think the 4 bytes after the header are a pointer into the segment table (which they're not; those 4 bytes represent the number of elements in the array), and boom, you've successfully corrupted your memory (or hopefully crashed). If you call delete [] on memory you used new, the allocator will think the 4 bytes after the header are the number of elements in the array (which they're not; those 4 bytes represent a pointer into the segment table), and boom, you've successfully corrupted your memory (or hopefully crashed).

If different block formats and allocation strategies are used, it's possible to completely destroy the allocator's linked list of free/allocated blocks by calling the wrong delete, and now you've got memory leaks, you're overwriting data and double allocating the same blocks of memory for different uses, etc. Bad, bad, bad mojo.

Mixing delete with new [] or delete [] with new is not safe! Yes, it's possible the allocator implements new as new [1] (which would be a valid way to do it), and delete as delete [], but banking on that idea is like playing Russian roulette (with a gun that has more than one round in it).

Writing a correct, proper, fast, and efficient allocator is very hard work and involves lots of tricks. The last thing you need as an allocator is someone screwing up your tricks and hacks by freeing memory wrong.

### #1Cornstalks

Posted 15 January 2013 - 11:27 AM

SiCrane mentions some very good points. I'm going to dive a little deeper into the internals of memory management and try to explain why the above is such a big problem.

There are various strategies for managing allocated memory. The allocator is what actually allocates the memory and frees it when you call new/delete. One very common allocation strategy is to request memory from the operating system when more is needed, but when its freed, don't immediately hand it back to the operating system. Keep it around. Why? Well, chances are the programmer is going to allocate more memory some time soon. If you give it all back to the OS right now, you'll just have to request more form the OS soon anyway (and these can all be pretty slow operations), so if the allocator hangs onto it, when you request more memory the allocator has some already available to give you. Yay, increase in speed! (there are other practical reasons why, but this is a big one)

Now, as you allocate memory and free it, your memory becomes fragmented. If you looked at it as one continuous block of memory, you'd have free chunks and allocated chunks mixed all over. How does the allocator keep track of what's allocated and what's free? Remember, this is the allocator! It can't just ask some other allocator for memory and keep a nice std::vector<ptr> of free and allocated chunks of memory. It's a pain in the butt to do, but here's a common way it's done:

Linked lists. In memory. When you allocate memory, the allocator does something like this:

void* malloc(size_t bytes) // same idea for new/new[] (horribly simplified, though)
{
void* ptr = RequestBytesFromOperatingSystem(bytes + HEADER_SIZE);

return (char*)ptr + HEADER_SIZE; // skip the header and give return the usable block to the user
}

The allocator allocates an extra few bytes to keep a header for each block of memory. This header usually says how large the block is, if the block is free or allocated and in use, if the next block (at ptr + bytes + HEADER_SIZE) is free or allocated and in use, and if the previous block is free or allocated and in use. If the block is free, the allocator might use some of the space in the block to store pointers to the previous and next free blocks (maintaining a linked list).

So now let's take this idea for memory blocks, and what SiCrane said above, and document them to figure out how a block of memory might look to the allocator

Potential structure of a memory block allocated by new (that is, this block is allocated and in use):
Upper 29 bits: size of this block in memory
Bit 2: 1 if previous block is free, 0 if previous block is allocated
</p><div>    Bit 1: 1 if next block is free, 0 if next block is allocated</div>
<div>    Bit 0: 1 if this block is free, 0 if this block is allocated</div>
<div>Pointer into segment table (4 bytes) (also acts as padding to maintain 8-byte alignment, like many CPUs need)</div>
<div>    Instead of wasting the padding, we'll store which segment into our segment table this block should be</div>
<div>    inserted into when its freed (so we don't have compute it when we free it, yay speed!)</div>
<div>User data (N bytes)</div>
<div>    This is the memory the programmer is actually able to use</div>
<div>
<div> </div>
<div>Potential structure of a memory block allocated by new [] (that is, this block is allocated and in use):</div>
</div>

<div>    Upper 29 bits: size of this block in memory</div>
<div>    Bit 2: 1 if previous block is free, 0 if previous block is allocated</div>
<div>    Bit 1: 1 if next block is free, 0 if next block is allocated</div>
<div>    Bit 0: 1 if this block is free, 0 if this block is allocated</div>
<div>Number of elements (4 bytes) (also acts as padding to maintain 8-byte alignment, like many CPUs need)</div>
<div>    Instead of wasting the padding, we'll use it to store the number of elements in this array</div>
<div>User data (N bytes)</div>
<div>    This is the memory the programmer is actually able to use</div>
<div> </div>
<div>
<div>Potential structure of a free block of memory (after it's been freed by delete or delete []):</div>
<div>    Upper 29 bits: size of this block in memory</div>
<div>    Bit 2: 1 if previous block is free, 0 if previous block is allocated</div>
<div>    Bit 1: 1 if next block is free, 0 if next block is allocated</div>
<div>    Bit 0: 1 if this block is free, 0 if this block is allocated</div>
<div>Pointer to the next free block (4 bytes)</div>
<div>    This way we can maintain a linked list of free blocks</div>
<div>Block data (N bytes)</div>
<div>    Junk</div>
<div>

There are various allocation strategies and memory block formats, but the above encapsulates some common practices and ideas shared by many allocators.

Now, when the allocator tries to free a block of memory, it's going to try to use the block's header (the first 4 bytes of the block), and the following 4 bytes (what those bytes represent depends on whether or not you called new or new [], and depending on whether you call delete or delete [] it will change how those bytes are interpreted). If you call the delete on memory you used new [], the allocator will think the 4 bytes after the header are a pointer into the segment table (which they're not; those 4 bytes represent the number of elements in the array), and boom, you've successfully corrupted your memory (or hopefully crashed). If you call delete [] on memory you used new, the allocator will think the 4 bytes after the header are the number of elements in the array (which they're not; those 4 bytes represent a pointer into the segment table), and boom, you've successfully corrupted your memory (or hopefully crashed).

If different block formats and allocation strategies are used, it's possible to completely destroy the allocator's linked list of free/allocated blocks by calling the wrong delete, and now you've got memory leaks, you're overwriting data and double allocating the same blocks of memory for different uses, etc. Bad, bad, bad mojo.

Mixing delete with new [] or delete [] with new is not safe! Yes, it's possible the allocator implements new as new [1] (which would be a valid way to do it), and delete as delete [], but banking on that idea is like playing Russian roulette (with a gun that has more than one round in it).

PARTNERS