I'm confused regarding
"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."
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:
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
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.