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

Most likely it will not work. malloc can not rearrange already allocated memory so it can't make a continuous free block of 20 byte. It can only ask the OS to get another page of memory from, of which it can chop of 20 bytes + header.

Answer 2

OS specific.

If it's a system that has virtual memory, malloc is just going to allocate another page of VM and add it to its heap, and then hand you the memory you need. The chunk of memory within the page has to be contiguous though. Interestingly, if your demand is bigger than the page size, the memory doesn't have to be contiguous in physical memory. Two pages of VM can be made contiguous, regardless of where they are located in physical memory.

If it's a system that does not have VM, then yes, all the memory you request needs to be contiguous in physical memory.

Answer 3

Standard malloc is defined in the C standard to allocate a contiguous block of memory (at least it appears so to you) - it will return a null pointer if the allocation fails.

At a lower level, the OS will be doing something like what kotlinski or Blank Xavier have described in their respective answers.

From §7.20.3 of the ISO/IEC 9899-1999 C Standard:

The pointer returned if the allocation (by calloc, realloc, or malloc) succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated).

It is not that explicit, but the paragraph mentions 'accessing an array of such objects', and in the C standard, arrays are:

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. (from §6.2.5)

Also note that subsequent calls to calloc, realloc, and malloc do not guarantee contiguity or ordering of memory (with other memory blocks already allocated).

This point is also specified in §7.20.3.

The order and contiguity of storage allocated by successive calls to the calloc, malloc, and realloc functions is unspecified.

Answer 4

This is platform specific. To your eyes, on the software level, it will always be presented as you malloc:ed 20 contiguous bytes. But on some platforms, e.g. with paged memory, these bytes do not really need to be contiguous when it comes down to the actual hardware - it will just appear so.

Answer 5

The question is kind of wrong.

In a typical OS, there exists the concepts of virtual memory and physical memory.

Physical memory exists typically in 4kb blocks, virtual memory likewise.

Each process has virtual memory - to each process the OS presents what appears to be the fully addressable memory range. So on a 32 bit machine, each process 'thinks' it has 4 GB of contigious memory.

In reality, the OS, behind the scenes, is busy mapping virtual memory allocations onto real blocks of physical memory. So a, say, 400kb virtual memory allocation, is mapped onto 100 physical blocks. Those physical blocks do not need to be contigious (and almost never are - nothing stops it from happening, but on a machine doing any kind of work, it's highly improbable) but the virtual memory allocation does need to be contigious.

So you can still run into virtual memory fragmentation. Here, a process requests a block of memory and there isn't, in that particular processes virtual memory map, a block of contigious virtual memory such that the request can be satisfied.

That problem is the problem you're thinking of.

Answer 6

From the ISO C99 standard:

7.20.3 Memory management functions
The order and contiguity of storage allocated by successive calls to the calloc, malloc, and realloc functions is unspecified. The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly deallocated). The lifetime of an allocated object extends from the allocation until the deallocation. Each such allocation shall yield a pointer to an object disjoint from any other object. The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

7.20.3.3 The malloc function
The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.

So in other words, if you ask for space for a 20-byte object, you get enough space in which to fit a 20-byte object.