views:

137

answers:

4

Possible Duplicate:
C programming : How does free know how much to free?

free() is called to deallocate the memory allocated by malloc() function call. From where does the free() find the information about the no. of bytes allocated by the malloc() function. I.e., how do you conform the no. of bytes allocated by the malloc() and where is this information stored.

-Surya

+3  A: 

This is implementation dependent. The heap stores that data in some manner that facilitates accessing it having a pointer returned by malloc() - for example, the block could store the number of bytes at the beginning and malloc() would return an offsetted pointer.

sharptooth
+6  A: 

Most implementations of C memory allocation functions will store accounting information for each block, either inline or separately.

One typical way (inline) is to actually allocate both a header and the memory you asked for, padded out to some minimum size. So for example, if you asked for 20 bytes, the system may allocate a 48-byte block:

  • 16-byte header containing size, special marker, checksum, pointers to next/previous block and so on.
  • 32 bytes data area (your 20 bytes padded out to a multiple of 16).

The address then given to you is the address of the data area. Then, when you free the block, free will simply take the address you give it and, assuming you haven't stuffed up that address or the memory around it, check the accounting information immediately before it.

Keep in mind the size of the header and the padding are totally implementation defined (actually, the entire thing is implementation-defineda but the inline-accounting-info option is a common one).

The checksums and special markers that exist in the accounting information are often the cause of errors like "Memory arena corrupted" if you overwrite them. The padding (to make allocation more efficient) is why you can sometimes write a little bit beyond the end of your requested space without causing problems (still, don't do that, it's undefined behaviour and, just because it works sometimes, doesn't mean it's okay to do it).


a I've written implementations of malloc in embedded systems where you got 128 bytes no matter what you asked for (that was the size of the largest structure in the system) and a simple non-inline bit-mask was used to decide whether a 128-byte chunk was allocated or not.

Others I've developed had different pools for 16-byte chunks, 64-bytes chunks, 256-byte chunks and 1K chunks, again using a bitmask to reduce the overhead of the accounting information and to increase the speed of malloc and free (no need to coalesce adjacent free blocks), particularly important in the environment we were working in.

paxdiablo
+2  A: 

When you allocate a block of memory, more bytes than you requested are allocated. How many depends on the implementation but here is an example:

struct MallocHeader {
    struct MallocHeader * prev, * next;
    size_t length;
    ... more data, padding, etc ...
    char data[0];
}

When malloc() allocates the memory from the free list, it will allocate size + sizeof(struct MallocHeader) and return the address of data. In free(), the offset of data in the struct MallocHeader is subtracted from the pointer you pass in and then it knows the size.

Aaron Digulla
A: 

This is implementation dependent - it depends on the libc implementation and also on the operating system implementation (more on the operating system implementation).

I haven't got a need to know such things but if you really want to you can create your own memory allocator.

By mistake I found out that in C++ when allocating with new[] operator stores the number of elements at the beginning of the allocated zone returning to the user the zone after the number of elements (On Visual Studio).

new[NUMBER] ---> [NUMBER (4bytes)]+[allocated area]
it returns the pointer to the allocated area
and probably when the delete[] operator is called
it looks 4 bytes before the [allocated area] to see
how much elements will be deleted
Iulian Şerbănoiu