How Do Malloc() and Free() Work

How do malloc() and free() work?

OK some answers about malloc were already posted.

The more interesting part is how free works (and in this direction, malloc too can be understood better).

In many malloc/free implementations, free does normally not return the memory to the operating system (or at least only in rare cases). The reason is that you will get gaps in your heap and thus it can happen, that you just finish off your 2 or 4 GB of virtual memory with gaps. This should be avoided, since as soon as the virtual memory is finished, you will be in really big trouble. The other reason is, that the OS can only handle memory chunks that are of a specific size and alignment. To be specific: Normally the OS can only handle blocks that the virtual memory manager can handle (most often multiples of 512 bytes e.g. 4KB).

So returning 40 Bytes to the OS will just not work. So what does free do?

Free will put the memory block in its own free block list. Normally it also tries to meld together adjacent blocks in the address space. The free block list is just a circular list of memory chunks which have some administrative data in the beginning. This is also the reason why managing very small memory elements with the standard malloc/free is not efficient. Every memory chunk needs additional data and with smaller sizes more fragmentation happens.

The free-list is also the first place that malloc looks at when a new chunk of memory is needed. It is scanned before it calls for new memory from the OS. When a chunk is found that is bigger than the needed memory, it is divided into two parts. One is returned to caller, the other is put back into the free list.

There are many different optimizations to this standard behaviour (for example for small chunks of memory). But since malloc and free must be so universal, the standard behaviour is always the fallback when alternatives are not usable. There are also optimizations in handling the free-list — for example storing the chunks in lists sorted by sizes. But all optimizations also have their own limitations.

Why does your code crash:

The reason is that by writing 9 chars (don't forget the trailing null byte) into an area sized for 4 chars, you will probably overwrite the administrative-data stored for another chunk of memory that resides "behind" your chunk of data (since this data is most often stored "in front" of the memory chunks). When free then tries to put your chunk into the free list, it can touch this administrative-data and therefore stumble over an overwritten pointer. This will crash the system.

This is a rather graceful behaviour. I have also seen situations where a runaway pointer somewhere has overwritten data in the memory-free-list and the system did not immediately crash but some subroutines later. Even in a system of medium complexity such problems can be really, really hard to debug! In the one case I was involved, it took us (a larger group of developers) several days to find the reason of the crash -- since it was in a totally different location than the one indicated by the memory dump. It is like a time-bomb. You know, your next "free" or "malloc" will crash, but you don't know why!

Those are some of the worst C/C++ problems, and one reason why pointers can be so problematic.

How do free and malloc work in C?

When you malloc a block, it actually allocates a bit more memory than you asked for. This extra memory is used to store information such as the size of the allocated block, and a link to the next free/used block in a chain of blocks, and sometimes some "guard data" that helps the system to detect if you write past the end of your allocated block. Also, most allocators will round up the total size and/or the start of your part of the memory to a multiple of bytes (e.g. on a 64-bit system it may align the data to a multiple of 64 bits (8 bytes) as accessing data from non-aligned addresses can be more difficult and inefficient for the processor/bus), so you may also end up with some "padding" (unused bytes).

When you free your pointer, it uses that address to find the special information it added to the beginning (usually) of your allocated block. If you pass in a different address, it will access memory that contains garbage, and hence its behaviour is undefined (but most frequently will result in a crash)

Later, if you free() the block but don't "forget" your pointer, you may accidentally try to access data through that pointer in the future, and the behaviour is undefined. Any of the following situations might occur:

the memory might be put in a list of free blocks, so when you access it, it still happens to contain the data you left there, and your code runs normally.
the memory allocator may have given (part of) the memory to another part of your program, and that will presumably have then overwritten (some of) your old data, so when you read it, you'll get garbage which might cause unexpected behaviour or crashes from your code. Or you will write over the other data, causing the other part of your program to behave strangely at some point in the future.
the memory could have been returned to the operating system (a "page" of memory that you're no longer using can be removed from your address space, so there is no longer any memory available at that address - essentially an unused "hole" in your application's memory). When your application tries to access the data a hard memory fault will occur and kill your process.

This is why it is important to make sure you don't use a pointer after freeing the memory it points at - the best practice for this is to set the pointer to NULL after freeing the memory, because you can easily test for NULL, and attempting to access memory via a NULL pointer will cause a bad but consistent behaviour, which is much easier to debug.

Malloc, free, and multiple pointers, how does it work?

You cannot predict the behavior of this function, as it is undefined behavior

From the reference:

Deallocates the space previously allocated by malloc(), calloc(), aligned_alloc, (since C11) or realloc().
If ptr is a null pointer, the function does nothing.
The behavior is undefined if the value of ptr does not equal a value returned earlier by malloc(), calloc(), realloc(), or aligned_alloc() (since C11).
—free, C++ Reference

Emphasis mine: your use of free in this context would involve freeing from a pointer that was not obtained from the use of any of those functions; it was obtained by transforming the pointer that was obtained from malloc, and thus is not valid.

My best guess at what might happen is a segmentation fault; but that's up to your compiler, and not something you or I can guarantee.

So do not do this.

C: Malloc and Free

First of all there is no need to cast the malloc

array = malloc(n * sizeof(char));

I have one question: Why wouldn't I just do char array[10];?

What will you do if you don't know how many storage space do you want (Say, if you wanted to have an array of arbitrary size like a stack or linked list for example)?

In this case you have to rely on malloc (in C99 you can use Variable Length Arrays but for small memory size).

The function malloc is used to allocate a certain amount of memory during the execution of a program. The malloc function will request a block of memory from the heap. If the request is granted, the operating system will reserve the requested amount of memory.

When the amount of memory is not needed anymore, you must return it to the operating system by calling the function free.

In simple: you use an array when you know the number of elements the array will need to hold at compile time. you use malloc with pointers when you don't know how many elements the array will need to be at compile time.

For more detail read Heap Management With malloc() and free().

How does malloc and free work with errors?

The answer to this question is that it is automatically freed.

The reason for this is that for C on Linux, memory is always tracked in two separate ways.

Each program keeps track of what memory it has allocated, and how large each allocation is. This is malloc-level tracking.
The operating system keeps track of which pieces of memory belong to which program. This is page-level tracking.

In other words, if a program fails to free a piece of memory, then the operating system still knows that that piece of memory belongs to that program. The memory can be freed when the program exits.

So, if the operating system can allocate memory to a program, and free it, why does malloc-level tracking even exist? When Linux allocates memory to a program, it can only do so in 4KB chunks called "pages." If you wanted to allocate 10 bytes to hold a string, it would be very wasteful to allocate a full page, and only use the first 10 bytes. For this reason, malloc() requests memory from the operating system¹ in 4KB pages, and cuts them into smaller pieces if you ask for a smaller piece. Then, it keeps track of each allocation.

If you forget to free a piece of memory, and your program exits, it does not matter, because the operating system will free the memory anyway. It's still wise to free memory in error paths, because someday you might want to change the program so that it recovers from the error instead of immediately exiting.

¹ I'm glossing over some details here.

Does using malloc in method, free in main work?

Mixing malloc freeing it with delete is explained in other answers.

I feel you want to know if malloc memory allocated in a method, return the pointer to main, and free the pointer in main will work or not ? Yes it can be done and free will clear the memory allocated in other methods provided you have the pointer pointing to that location.

How to correctly use malloc and free memory?

Both are fine. The only difference is that the former approach would crash if you tried to free myPtr a second time.

Depending on the language you're using, the malloc line could be tidied up a little.

Using sizeof(*myPtr) is less prone to bugs when you later refactor. If you're using C, the cast is also unnecessary

double* myPtr = malloc(sizeof(*myPtr)*5);

As pointed out by WhozCraig, if you're using C++, there are much easier ways to allocate an array

 std::vector<double> ar(5);

gives you an array of 5 doubles that will grow its storage if required and automatically free its memory when it goes out of scope.

How are malloc and free implemented?

On linux, malloc and free are not system calls. malloc/free obtains memory from the kernel by extending and shrinking(if it can) the data segment using the brk system calls as well as obtaining anonymous memory with mmap - and malloc manages memory within those regions. Some basic information any many great references can be found here

C: malloc(), free() and then again malloc() does work same always?

It happens in practice because re-using a just-freed chunk of memory is usually the best choice. It's probably still hot in cache, and it means malloc's free-list can be shortened (instead of leaving that block on the free list and getting a new block from the OS).

It also means malloc probably doesn't need any system calls to satisfy this request. Small free() calls are typically not returned to the OS right away (because usually they can't be, because they're just part of a page). So typical malloc implementations put them on a free-list.

So this little experiment has told you something about the internal implementation of malloc on the particular C implementation you tried it on. As I think you realize from the question phrasing, this is undefined behaviour and should never be relied upon.

It's not really specific to CPU architecture. AFAIK, GNU libc's malloc uses the same algorithms on every architecture.

Even on a C implementation that does work this way, there are many ways for this to break: a signal handler could run between the free and the second malloc, and take the block. In multithreaded code, another thread could take that block between the free and the malloc. (Although this is less likely: each thread would usually use its own small pool).

A large buffer usually would be handed back to the OS inside the free() call, so the next malloc() would have to get fresh memory from the OS again. See M_MMAP_THRESHOLD in mallopt(3) for an explanation of that tunable parameter in glibc's malloc. M_PERTURB provides similar functionality to what Adrian describes for MSVC++ debug builds: breaking code that has use-after-free bugs, and breaking code that depends on malloced memory being zeroed or something (use calloc to efficiently get zeroed memory).

How Do Malloc() and Free() Work