I have read in the K&R book that "the space that malloc manages may not be contiguous. each block contains size ,a pointer to next block.". But when i did google i saw that most of the people are saying that malloc always does contiguous memory allocation. So please clear this doubt .What is the fact? The space that malloc manages is always contiguous or may or may not be contiguous.
3 Answers
A single block of memory returned by malloc, calloc or realloc will always be contiguous.
The next block of memory returned by a separate alloc call can be at any address and does not need to be contiguous with the first block.
Look at the diagram on the very page you read that sentence:
The region with dots is not owned by malloc, and is right between two regions that malloc manages. The region not owned by malloc is mostly likely allocated by another part of the program (for example, using mmap(2)). It could also just be not allocated.
Despite this 'hole' in the region of memory managed by malloc, malloc (and it's family of functions) only allocate blocks of memory that are contiguous.
So, the region managed by malloc could be discontiguous, but the blocks allocated by malloc are contiguous.
The memory segment you receive from a single call to malloc() is always contiguous. There's no warranty on the segments returned from different calls. It's possible that you get that impression at program start on the first calls to malloc, but as memory is returned to the heap with free() the memory returned is reused and finally you end with more or less amount of dispersion, making different calls to return completely unrelated pointers.
On other side, malloc() uses sbrk(2) system call that increases/decreases the size of the data segment, if possible. But in the case it cannot use sbrk(), malloc() uses memmap() to get one or more heaps to operate. Memmap() was not available in unix systems when that book was written, so in principle things can have changed a lot since then. Those heaps (mmap()ed) are mapped into the virtual space of the process, based on many possible situations by the kernel, not by malloc(), like the loading of dynamic shared objects, and this clashes with the enforcement of continuity in the address space. Probably the addresses will show ranges of discontinous memory interspersed with other ranges of completely different things, like physical memory attachments (like video memory if the operating system offers this service) memory mapped files, shared libraries, etc.
On other side, malloc must allocate some data for each chunk of memory that it gives to you.... Many implementations locate this chunk on one side of the given segment, so even if the chuncks were contiguous, you cannot normally use the memory between them or you'll corrupt the memory malloc() uses to handle the heap.
Related