How malloc works? [duplicate]

Question

This question already has answers here:

Closed 9 years ago.

Possible Duplicate:
How do free and malloc work in C?

Consider a scenario where i have to allocate some 20 bytes of memory through malloc. For the function call to malloc() to be successful, should the 20 bytes be available contiguously in memory or can it be scattered? For eg, in the above case, if there are 4 or 5 chunks of 10 bytes each, will malloc work? Or is this OS specific or compiler-specific?

Answer 1

The memory has to be continuous - what you are mentioning is generally referred to as memory fragmentation, and is a real problem for applications acquiring and freeing memory very often.

Answer 2

The call to malloc will either succeed in returning a logically contiguous block of memory from your program's HEAP memory space equal to the size requested or it will fail with a NULL pointer. "Logically contiguous" means that with a malloc of this type:

int *ip;      /* Nothing yet allocated (other than the size of a pointer... */
int ar[100];  /* 100 ints on the STACK */
ip = (int *)malloc(sizeof ar);   /* if that succeeds, 100 ints on the HEAP */

will allocate space for 100 ints on your OS on the HEAP and return either NULL or the pointer. Separately, the array ar is allocated on the STACK. Each array will be laid out with all the ints logically next to each other, at least as far your program knows. If they were not next to each other, you would not be able to address these blocks as arrays with the array[offset] notation or with pointer arithmetic.

You can then access either STACK or HEAP blocks of memory with an array access or pointer access interchangeably like this:

ip[2]=22;        /* the second element of ip[] is '22' */
*(ar+33)=3333;   /* the 33 element of ar is '3333' */

i=*(ip+2);       /* assign using pointers */
j=ar[33];        /* assign using array offsets */

If the memory block returned by malloc were not logically contiguous to your program, you would not be able to access the block with pointer arithmetic or array subscripting.

Behind the scenes, your OS may move other blocks of memory that are moveable, use virtual memory, swap other items to virtual memory, etc, in order to increase the HEAP allocated to your program. Malloc can either be a very fast or very expensive call -- depending what else is going on on that system and the HEAP space allocated to your program.

HEAP memory (that part accessed with dynamic system calls in C) is potentially subject to fragmentation. Say you allocated the number of 20 byte blocks where memory becomes scarce. Now image that you free every other block of those blocks. You will have highly fragmented memory since blocks allocated with malloc cannot be moved if it effects the pointer that the program uses to access the block. (It can be moved transparently, but don't count on that being efficient.)

If you are making many calls for HEAP memory, consider changing your logic to use realloc to grow and shrink the memory as needed. A big 'gotcha' with realloc is the pointer to your existing data may change, so only use 1 pointer to it. Realloc allows the OS to move the data as needed to have a better fit with what is available on the HEAP. You will (mostly) avoid the potential for memory fragmentation that way.

For quick blocks of 20 bytes, consider using the STACK. That is what it is for. Look at this SO post to see characteristics of STACK vs HEAP.

Read the C Guide of calloc, malloc, realloc, free for more info.