what happens in the kernel during malloc?

Question

I was asked this question during an interview. What they wanted to know was when the user calls malloc(4) to allocate 4 bytes of memory how does the operating system (Linux) respond? Which subsystem responds to this system call?

I told him that malloc() will be serviced by the memory management subsystem. The malloc() implementation will go through the list of free memory(physical memory), we will call it free list, and find an appropriate chunk that is greater than or equal to 4 Bytes. Once it finds such a chunk, it will be deleted from free list and added to a used list. Then that physical memory will be mapped to the process heap vma struct. He didn't seem to be quite satisfied with this answer.How does the buddy system fit into this? Any help would be greatly appreciated.

Solution 1

When user space applications call malloc(), that call isn't implemented in the kernel. Instead, it's a library call (implemented glibc or similar).

The short version is that the malloc implementation in glibc either obtains memory from the brk()/sbrk() system call or anonymous memory via mmap(). This gives glibc a big contiguous (regarding virtual memory addresses) chunk of memory, which the malloc implementation further slices and dices in smaller chunks and hands out to your application.

Here's a small malloc implementation that'll give you the idea, along with many, many links.

Note that nothing cares about physical memory yet -- that's handled by the kernel virtual memory system when the process data segment is altered via brk()/sbrk() or mmap(), and when the memory is referenced (by a read or write to the memory).

To summarize:

1. malloc() will search its managed pieces of memory to see if there's a piece of unused memory that satisfy the allocation requirements.
2. Failing that, malloc() will try to extend the process data segment(via sbrk()/brk() or in some cases mmap()). sbrk() ends up in the kernel.
3. The brk()/sbrk() calls in the kernel adjust some of the offsets in the struct mm_struct of the process, so the process data segment will be larger. At first, there will be no physical memory mapped to the additional virtual addresses which extending the data segment gave.
4. When that unmapped memory is first touched (likely a read/write by the malloc implementation) a fault handler will kick in and trap down to the kernel, where the kernel will assign physical memory to the unmapped memory.

Solution 2

malloc does not deal with physical memory directly. It deals with paged virtual memory - although I'm not certain if it's true for every architecture out there.

When your program tries to allocate memory and the free list doesn't contain a chunk of equal or larger size than the requested size, an entire new page is allocated. The page size is architecture dependent (4096 bytes on x86). Page allocation is something only the kernel can perform, thus a malloc call may cause a system call. The new address is then added to the free list, and malloc manipulates the free list according to its implemention (check glibc for example).