How do malloc and free work

Question

I want to know how malloc and free work   int main         unsigned char  p    unsigned char  malloc 4 sizeof unsigned char        memset p 0 4       strcpy  char  p  abcdabcd         deliberately storing 8bytes       cout  lt  lt  p      free p      Obvious Crash  but I need how it works and why crash      cout  lt  lt  p      return 0      I would be really grateful if the answer is in depth at memory level  if it s possible

User · Answer

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.

User · Answer

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

User · Answer

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

User · Answer

It s also important to realize that simply moving the program break pointer around with brk and sbrk doesn t actually allocate the memory  it just sets up the address space  On Linux  for example  the memory will be  backed  by actual physical pages when that address range is accessed  which will result in a page fault  and will eventually lead to the kernel calling into the page allocator to get a backing page

User · Answer

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

User · Answer

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    How to get new memory How to store it -   list or other structure  multiple lists for memory chunks of different size  and so on    What to do if the user requests more memory than currently available   request more memory from OS  join some of the existing blocks  how to join them exactly        What to do when the user frees memory Debug allocators may give you bigger chunk that you requested and fill it some byte pattern  when you free the memory the allocator can check if wrote outside of the block   which is probably happening in your case

User · Answer

One implementation of malloc free does the following    Get a block of memory from the OS through sbrk    Unix call   Create a header and a footer around that block of memory with some information such as size  permissions  and where the next and previous block are  When a call to malloc comes in  a list is referenced which points to blocks of the appropriate size  This block is then returned and headers and footers are updated accordingly

User · Answer

As aluser says in this forum thread      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

User · Answer

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

User · Answer

Memory protection has page-granularity and would require kernel interaction  Your example code essentially asks why the example program doesn t trap  and the answer is that memory protection is a kernel feature and applies only to entire pages  whereas the memory allocator is a library feature and it manages    without enforcement    arbitrary sized blocks which are often much smaller than pages   Memory can only be removed from your program in units of pages  and even that is unlikely to be observed   calloc 3  and malloc 3  do interact with the kernel to get memory  if necessary  But most implementations of free 3  do not return memory to the kernel1  they just add it to a free list that calloc   and malloc   will consult later in order to reuse the released blocks   Even if a free   wanted to return memory to the system  it would need at least one contiguous memory page in order to get the kernel to actually protect the region  so releasing a small block would only lead to a protection change if it was the last small block in a page   So your block is there  sitting on the free list  You can almost always access it and nearby memory just as if it were still allocated  C compiles straight to machine code and without special debugging arrangements there are no sanity checks on loads and stores  Now  if you try and access a free block  the behavior is undefined by the standard in order to not make unreasonable demands on library implementators  If you try and access freed memory or meory outside an allocated block  there are various things that can go wrong    Sometimes allocators maintain separate blocks of memory  sometimes they use a header they allocate just before or after  a  footer   I guess  your block  but they just might want to use memory within the block for the purpose of keeping the free list linked together  If so  your reading the block is OK  but its contents may change  and writing to the block would be likely to cause the allocator to misbehave or crash  Naturally  your block may be allocated in the future  and then it is likely to be overwritten by your code or a library routine  or with zeroes by calloc    If the block is reallocated  it may also have its size changed  in which case yet more links or initialization will be written in various places  Obviously you may reference so far out of range that you cross a boundary of one of your program s kernel-known segments  and in this one case you will trap    Theory of Operation  So  working backwards from your example to the overall theory  malloc 3  gets memory from the kernel when it needs it  and typically in units of pages  These pages are divided or consolidated as the program requires  Malloc and free cooperate to maintain a directory  They coalesce adjacent free blocks when possible in order to be able to provide large blocks  The directory may or may not involve using the memory in freed blocks to form a linked list   The alternative is a bit more shared-memory and paging-friendly  and it involves allocating memory specifically for the directory   Malloc and free have little if any ability to enforce access to individual blocks even when special and optional debugging code is compiled into the program     1  The fact that very few implementations of free   attempt to return memory to the system is not necessarily due to the implementors slacking off  Interacting with the kernel is much slower than simply executing library code  and the benefit would be small  Most programs have a steady-state or increasing memory footprint  so the time spent analyzing the heap looking for returnable memory would be completely wasted  Other reasons include the fact that internal fragmentation makes page-aligned blocks unlikely to exist  and it s likely that returning a block would fragment blocks to either side  Finally  the few programs that do return large amounts of memory are likely to bypass malloc   and simply allocate and free pages anyway

User · Answer

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

User · Answer

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

User · Answer

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

[c++] How do malloc() and free() work?

Examples related to c++

Examples related to c

Examples related to memory-management

Examples related to malloc

Examples related to free