Hi,
I am curious to know about the in details about how the malloc and free works.
int main()
{
unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
memset(p,0,4);
strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
cout << p;
free(p); // Obvious Crash, but I need how it works and why crash.
cout << p;
return 0;
}
It would be really greatfull to you all if answer is in depth @ memory level if possible. :).
Thanks very much in advance.
If you're into learning by example, then this is pretty deep as far as "explanations" go. :)
One implementation of malloc/free does the following:
Here is a lab from Purdue that describes how to implement malloc and the algorithm I described, but in more detail.
This has nothing specifically to do with malloc and free. Your program exhibits undefined behaviour after you copy the string - it could crash at that point or at any point afterwards. This would be true even if you never used malloc and free, and allocated the char array on the stack or statically.
It's hard to say because the actual behaviour is different between different compilers/runtimes. Even debug/release builds have different behaviour. Debug builds of VS2005 will insert markers between allocations to detect memory corruption, so instead of a crash, it will assert in free().
Regards,
Sebastiaan
In theory, malloc gets memory from the operating system for this application. However, since you may only want 4 bytes, and the OS needs to work in pages (often 4k), malloc does a little more than that. It takes a page, and puts it's own information in there so it can keep track of what you have allocated and freed from that page.
When you allocate 4 bytes, for instance, malloc gives you a pointer to 4 bytes. What you may not realize is that the memory 8-12 bytes before your 4 bytes is being used by malloc to make a chain of all the memory you have allocated. When you call free, it takes your pointer, backs up to where it's data is, and operates on that.
When you free memory, malloc takes that memory block off the chain... and may or may not return that memory to the operating system. If it does, than accessing that memory will probably fail, as the OS will take away your permissions to access that location. If malloc keeps the memory ( because it has other things allocated in that page, or for some optimization ), then the access will happen to work. It's still wrong, but it might work.
DISCLAIMER: What I described is a common implementation of malloc, but by no means the only possible one.
Well it depends on the memory allocator implementation and the OS.
Under windows for example a process can ask for a page or more of RAM. The OS then assigns those pages to the process. This is not, however, memory allocated to your application. The CRT memory allocator will mark the memory as a contiguous "available" block. The CRT memory allocator will then run through the list of free blocks and find the smallest possible block that it can use. It will then take as much of that block as it needs and add it to an "allocated" list. Attached to the head of the actual memory allocation will be a header. This header will contain various bit of information (it could, for example, contain the next and previous allocated blocks to form a linked list. It will most probably contain the size of the allocation).
Free will then remove the header and add it back to the free memory list. If it forms a larger block with the surrounding free blocks these will be added together to give a larger block. If a whole page is now free the allocator will, most likely, return the page to the OS.
It is not a simple problem. The OS allocator portion is completely out of your control. I recommend you read through something like Doug Lea's Malloc (DLMalloc) to get an understanding of how a fairly fast allocator will work.
Edit: Your crash will be caused by the fact that by writing larger than the allocation you have overwritten the next memory header. This way when it frees it gets very confused as to what exactly it is free'ing and how to merge into the following block. This may not always cause a crash straight away on the free. It may cause a crash later on. In general avoid memory overwrites!
Your strcpy line attempts to store 9 bytes, not 8, because of the NUL terminator. It invokes undefined behaviour.
The call to free may or may not crash. The memory "after" the 4 bytes of your allocation might be used for something else by your C or C++ implementation. If it is used for something else, then scribbling all over it will cause that "something else" to go wrong, but if it isn't used for anything else, then you could happen to get away with it. "Getting away with it" might sound good, but is actually bad, since it means your code will appear to run OK, but on a future run you might not get away with it.
With a debugging-style memory allocator, you might find that a special guard value has been written there, and that free checks for that value and panics if it doesn't find it.
Otherwise, you might find that the next 5 bytes includes part of a link node belonging to some other block of memory which hasn't been allocated yet. Freeing your block could well involved adding it to a list of available blocks, and because you've scribbled in the list node, that operation could dereference a pointer with an invalid value, causing a crash.
It all depends on the memory allocator - different implementations use different mechanisms.
malloc and free are implementation dependent. A typical implementation involves partitioning available memory into a "free list" - a linked list of available memory blocks. Many implementations artificially divide it into small vs large objects. Free blocks start with information about how big the memory block is and where the next one is, etc.
When you malloc, a block is pulled from the free list. When you free, the block is put back in the free list. Chances are, when you overwrite the end of your pointer, you are writing on the header of a block in the free list. When you free your memory, free() tries to look at the next block and probably ends up hitting a pointer that causes a bus error.
How malloc() and free() works depends on the runtime library used. Generally, malloc() allocates a heap (a block of memory) from the operating system. Each request to malloc() then allocates a small chunk of this memory be returning a pointer to the caller. The memory allocation routines will have to store some extra information about the block of memory allocated to be able to keep track of used and free memory on the heap. This information is often stored in a few bytes just before the pointer returned by malloc() and it can be a linked list of memory blocks.
By writing past the block of memory allocated by malloc() you will most likely destroy some of the book-keeping information of the next block which may be the remaining unused block of memory.
One place where you program may also crash is when copying too many characters into the buffer. If the extra characters are located outside the heap you may get an access violation as you are trying to write to non-existing memory.
Your program crashes because it used memory that does not belong to you. It may be used by someone else or not - if you are lucky you crash, if not the problem may stay hidden for a long time and come back and bite you later.
As far as malloc/free implementation goes - entire books are devoted to the topic. Basically the allocator would get bigger chunks of memory from the OS and manage them for you. Some of the problems an allocator must address are:
There's a sample implementation of malloc() and free() in The Book (Kernighan and Ritchie "The C Programming Language"). Since you had to ask, you haven't read it - go forth and read it, and repent of your sinful ways. :D
Ok some answers about malloc where already posted.
The more interesting part is how free works: (and thus direction also malloc 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 of your 2 or 4 GB of virtual memory with gaps. This should be avoided of course, since as soon as the virtual memory is finished, you will be in really big trouble. The other reason of course 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 eg. 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 melt together adjacent blocks in the address space. The free block list is just a circular list of memory chunks which have of course some admin 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 location, malloc looks for a new chunk of memory when needed. It is scanned before it calls for new memory from the OS. When a chunk is found that is bigger then the needed memory, it is just 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 8 chars into an area sized for 4 chars, you will probably overwrite the admin-data stored for an other 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 admin-data and therefore stumple over an overwritten pointer. This will crash the system.
This is a rather graceful behaviour. I have also seen situations, where a runnaway pointer somewhere has overwritten data in the memory-free-list and the system did not immediately crash but some subroutines later. In a just medium complex system such problems can be really, really hard to debug! In the one case I was involved, it took us several days to find the reason of the dump -- since it was in a total different location as the one in dump happened. It is like a time-bomb. You know, your next "free" or "malloc" will crash, but you don't know why!
That are the worst C/C++ problems and one reason, pointers can be so problematic.
simplest answer : Your process has a region of memory, from address x to address y, called the heap. All your malloc'd data lives in this area. malloc() keeps some data structure, let's say a list, of all the free chunks of space in the heap. When you call malloc, it looks through the list for a chunk that's big enough for you, returns a pointer to it, and records the fact that it's not free any more as well as how big it is. When you call free() with the same pointer, free() looks up how big that chunk is and adds it back into the list of free chunks(). If you call malloc() and it can't find any large enough chunk in the heap, it uses the brk() syscall to grow the heap, i.e. increase address y and cause all the addresses between the old y and the new y to be valid memory. brk() must be a syscall; there is no way to do the same thing entirely from userspace.
malloc() is system/compiler dependent so it's hard to give a specific answer. Basically however it does keep track of what memory it's allocated and depending on how it does so your calls to free could fail or succeed.
malloc() and free() don't work the same way on every O/S.