In practice this means that any allocation that doesn’t fit 2
n
∗ P AGE SIZE
is rounded up to the next power-of-two boundary. The n above is called the
order of the allocation. We will evaluate later how much memory this rounding
wastes.
A disadvantage of the buddy allocator is fragmentation. Since the power-of-
two objects also have to be aligned to power-of-two areas in memory when the
system is running for some time it tends to become difficult to allocate objects
The Linux implementation has some supp ort for caching pages locally per
CPU and per node as a p e rformance optimization. It also s upports memory
policies for NUMA optimization
4
.
More details on buddy allocators can be found in [3] or in [2]
2.4 Important users of the page allocator
The Page allocator is normally used to allocate page tables for the MMU
5
All
the other allocators like slab (except the early ones) also get their memory from
the page allocator. The major user is the page cache which is described next.
2.5 Page cache
The page cache manages cached file data and anonymous memory that is used
by programs. This includes all program text and data (except for the kernel),
file data that has been read or written and file system meta data.
When a program runs all the memory it can see directly, without accessing
it indirectly by calling some kernel service, is stored in the page cache.
The state of the page cache for the whole system can be examined using the
/proc/meminfo and /proc/zoneinfo files. Counters for individual proces ses are
in /proc/self/stat and /proc/self/statm. The easiest way to examine it is with
various front end tools that read these numbers like free, vmstat, ps, top, etc.
An overview of the state of the various zones can be also gotten by enabling
the sys-req key
6
and pressing Alt-Sysrq-m
7
. This will dump the state of the
various zones and how much memory is still free.
2.6 Slab allocator
Slab is a allocator that caches objects that caches objects that are typically
smaller than a page. Slab actually supports objects larger than a page too for
consistency, but most objects are smaller and slab isn’t very good at dealing
with large objects. Most objects handled in the kernel are allocated by the slab
allocator.
The kernel objects are managed in slab caches. A slab cache contains objects
of the same type. It can cache free together and allocated objects. The free
objects can b e in a ”constructed” state to avoid some overhead in repeatedly
4
For example, on a NUMA system it tries to place the allocation on memory local to the
CPU which is requesting the memory.
5
There can be exceptions: on a 32Bit PAE system the highest page table level is allocated
by slab.
6
See Documentation/sysrq.txt in the kernel source.
7
This ho t key can vary by architecture