malloc and heap: extra memory for storing the size and linked list information?

Question

I have a simple question about the heap and malloc:

When we allocate some memory space using malloc as following:

int *p;
p = (int*) malloc (10*sizeof(int));

It actually allocates 10 words in the heap. However, my question is:

The actual memory space used is really 10 words?

Or there are other extra space needed for storing the value of memory size?

Or, even, because the heap is structured as Linked list, is there other memory space being used for storing the address which points to the next node of the list in the heap?

Answer 1

It is completely implementation dependent.

a) It could have a few bytes before each allocated node which contains the size of the node, pointer to the next node, and maybe a previous node pointer and the type of node.

b) The returned item may have nothing else around it except other allocations. A structure elsewhere keeps track of what is allocated and what is free, perhaps by a bitmap or a miniature parallel list.

c) Another variation provides several arrays of fixed sized chunks. One array may provide 32-byte blocks; another 128-byte blocks, etc. A bitmap for each array manages allocations.

d) The most minimal implementation I have seen ignores free() completely (that is, free() is a no op) and allocates the next piece of the pool at each malloc().

---

By far, the most commonly used modern technique is a. Variant b is used in many filesystems like NTFS and FAT. Option c was/is favored in many DEC operating systems, especially for kernel use. Option d is used by a few minimalist embedded environments with a suitable caveat.

In most implementations, the requested allocation is rounded up to some natural multiple (usually of 2, 8, 16, etc.) convenient for the algorithm. So a series of allocations of 5, 3, 8, 7, 4, 1, and 15 might each be regarded as a 16 byte request.