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

Question

In C programming, you can pass any kind of pointer you like as an argument to free, how does it know the size of the allocated memory to free? Whenever I pass a pointer to some function, I have to also pass the size (ie an array of 10 elements needs to receive 10 as a parameter to know the size of the array), but I do not have to pass the size to the free function. Why not, and can I use this same technique in my own functions to save me from needing to cart around the extra variable of the array's length?

Answer 1

The heap manager stored the amount of memory belonging to the allocated block somewhere when you called malloc.

I never implemented one myself, but I guess the memory right in front of the allocated block might contain the meta information.

Answer 2

When you call malloc(), you specify the amount of memory to allocate. The amount of memory actually used is slightly more than this, and includes extra information that records (at least) how big the block is. You can't (reliably) access that other information - and nor should you :-).

When you call free(), it simply looks at the extra information to find out how big the block is.

Answer 3

malloc() and free() are system/compiler dependent so it's hard to give a specific answer.

More information on this other question.

Answer 4

From the comp.lang.c FAQ list: How does free know how many bytes to free?

The malloc/free implementation remembers the size of each block as it is allocated, so it is not necessary to remind it of the size when freeing. (Typically, the size is stored adjacent to the allocated block, which is why things usually break badly if the bounds of the allocated block are even slightly overstepped)

Answer 5

To answer the second half of your question: yes, you can, and a fairly common pattern in C is the following:

typedef struct {
    size_t numElements
    int elements[1]; /* but enough space malloced for numElements at runtime */
} IntArray_t;

#define SIZE 10
IntArray_t* myArray = malloc(sizeof(intArray_t) + SIZE * sizeof(int));
myArray->numElements = SIZE;

Answer 6

On a related note GLib library has memory allocation functions which do not save implicit size - and then you just pass the size parameter to free. This can eliminate part of the overhead.

Answer 7

There are free courses on iTunes University (University of Stanford): Programming Paradigms in which the answer to your question is very well explained.

Answer 8

This answer is relocated from http://stackoverflow.com/questions/1963745/how-does-free-know-how-much-memory-to-deallocate where I was abrubtly prevented from answering by an apparent duplicate question. This answer then should be relevant to this duplicate:

For the case of malloc, the heap allocator stores a mapping of the original returned pointer, to relevant details needed for freeing the memory later. This typically involves storing the size of the memory region in whatever form relevant to the allocator in use, for example raw size, or a node in a binary tree used to track allocations, or a count of memory "units" in use.

free will not fail if you "rename" the pointer, or duplicate it in any way. It is not however reference counted, and only the first free will be correct. Additional frees are "double free" errors.

Attempting to free any pointer with a value different to those returned by previous mallocs, and as yet unfreed is an error. It is not possible to partially free memory regions returned from malloc.

Answer 9

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-defined^a 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.