Linux – Heap Memory and Slab allocation

cheap-memorylinuxmallocmemory-management

I'm confused regarding heap and free list. I have a few questions and I have my own understanding of how malloc works in C. Please correct me if I'm wrong.

  • Is the heap memory organized as a linked list (free list) of data
    blocks ?
  • Is there a difference between heap memory and free list ?

My understanding of storage allocation (open for improvement) :-
When we call malloc, it allocates memory in the heap, and it does so by picking a data block of suitable size from the free list, right ?

When a certain block of memory is returned by malloc, it is removed from the free-list and the physical address of that block of memory is updated in the page table.

When the memory is free'd using free(), the data block is inserted back in the free-list, and possibly , to reduce fragmentation, conjoined with neighbouring block, and the present bit in the page table entry is cleared.

So the entire heap is a free-list(linked list of free blocks) + allocated data blocks .

Is that a comprehensive picture of storage allocation ?

EDIT : From Linux Kernel Development (Robert Love) Chapter on memory Management , Slab allocation

"A free list contains a block of available, already allocated, data
structures. When code requires a new instance of a data structure, it
can grab one of the structures off the free list rather than allocate
the sufficient amount of memory and set it up for the data structure.
Later, when the data structure is no longer needed, it is returned to
the free list instead of deallocated. In this sense, the free list
acts as an object cache, caching a frequently used type of object."

Free-list is mentioned as a "block of available, allocated data structure."

  • How is it allocated, when it is in a free-list ?
  • And how is returning a block of memory to free list _not_ the same as deallocating that block ?
  • How is slab allocation different from storage allocation

Best Answer

malloc() isn't really related to the page table; it allocates virtual addresses, and the kernel is responsible for keeping track of where the pages are actually stored in physical RAM or on disk.

malloc() interacts with the kernel via the brk() system call, which asks the kernel to allocate more pages to the process, or releases pages back to the kernel. So there are really two levels of memory allocation:

  • The kernel allocates pages to a process, making those pages unavailable for use by other processes. From the kernel's standpoint, the pages can be located anywhere and their locations are tracked by the page table, but from the process's standpoint, it's a contiguous virtual address space. The "program break" that brk() manipulates is the boundary between addresses that the kernel will let you access (because they correspond to allocated pages) and addresses that will cause a segmentation fault if you try to access them.
  • malloc() allocates variable-sized portions of the program's data segment for use by the program. When there's not enough free space within the current size of the data segment, it uses brk() to get more pages from the kernel, making the data segment bigger. When it finds that some space at the end of the data segment is unused, it uses brk() to give the unused pages back to the kernel, making the data segment smaller.

Note that pages can be allocated to a process (by the kernel) even if the program running in that process isn't actually using the pages for anything. If you free() a block of memory that's located in the middle of your data segment, the implementation of free() can't use brk() to shrink the data segment because there are still other allocated blocks at higher addresses. So the pages remain allocated to your program from the kernel standpoint, even though they're "free space" from the malloc() standpoint.

Your description of how a free list works sounds right to me, though I'm no expert in how memory allocators are implemented. But the quote you posted from Robert Love sounds like it's talking about memory allocation within the Linux kernel, which is unrelated to memory allocation by malloc() within a userspace process. That kind of free list probably works differently.

Related Topic