Page management in OS kernels

Question

I looked at some old OS theory books of mine and noticed that one glaring omission in all of these OS books is how to actually keep track of physical pages that are free (i.e. algorithms for actually implementing the free list). I know pretty well how userland memory allocators work, but a big difference with physical page allocation is that fragmentation of physical pages shouldn't be an issue, since the page table can just pick and choose the physical pages without having to care about whether they are contiguous or not. Since avoiding fragmentation is one of the main concerns of userland allocators, it seems like physical page allocation is fundamentally a different problem. I guess that this is not completely accurate if one wants to support superpages to reduce pressure on the TLB.

My question: What are techniques are used in modern high-performance kernels for this problem? Also, does this problem become significantly more complicated in NUMA systems?

Answer 1

Page frame management is conceptually very simple; all you really need is a linked list. However, there are two main factors which complicate things:

• DMA. DMA is one of the few things that might need a physical buffer larger than a page in size. In addition, there are legacy devices to contend with; on x86, for example, 32-bit devices can only do DMA from physical addresses below the 4G limit. For ISA it's even worse.
• Cache colouring, which is an extremely important optimisation.

Most operating systems use surprisingly simple techniques.

Windows, for example, just uses a bunch of linked lists (or at least it did, last time anyone said anything about it). It's hard to say since we can't see the source code, but there are probably N*M linked lists where N is the number of possible states a page can be in (e.g. in-use, free, waiting to be paged out) and M is the number of colours.

Linux famously uses a buddy allocator to manage physical pages, which is only slightly more complicated than a bunch of linked lists when you think about it.

Probably the most sophisticated management scheme that has been documented extensively is that of Solaris. See Bonwick & Adams, Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, USENIX 2001. There is also an extended discussion in the book Solaris Internals. The Solaris slab allocator goes to a lot of trouble to avoid lock contention, cache thrashing, and the like, and also can tune its implementation for different data types as needed.

What's interesting is that Solaris uses the same memory allocator to handle page frames that it uses to handle kernel objects, by nesting slab allocators inside slab allocators. The paper is definitely worth a read.