Linux memory allocator
2023-03-14 | Mani Kumar
Basic concepts and data structures of memory allocation in Linux kernel v6.2.
Physical memory
---------------
* Linux kernel detects the physical memory at boot time.
* Physical memory may start at a low (0x0) address and end at a high (2^N)
address spanning contiguous range.
* But in practice it may not be contiguous or start at 0x0 address.
_What is physical memory architecture?_
---
Physical memory architecture
----------------------------
### Uniform Memory Access (UMA)
* In general purpose computers such as desktops all CPUs access the memory
uniformly in the same way a single processor accesses it.
* The processors balance the access to memory.
* Symmetric Multi-Processor (SMP) systems balance the memory access using
system bus.
---
### Non Uniform Memory Access (NUMA)
* In large-scale machines such as servers with multi-processor the memory
arranged as "nodes" have non-uniform access time.
* In this arrangement a node is an independent memory subsystem local to one
or more processors.
* Accessing memory in node local to a CPU is faster than non-local node but
the memory has a single address space for use by any CPU.
_How Linux kernel represents the physical memory?_
_What data structures describe the physical memory in Linux kernel?_
---
Physical Memory Models
----------------------
### FLATMEM
* This the simplest memory model and is suitable for non-NUMA systems with
contiguous physical memory.
* In this model `mem_map` global array maps into the entire physical memory.
* Each element of this array is of type `struct page` which describes a page
in the physical memory.
_Drawback of this model is it can’t handle discontiguous physical address._
---
### SPARSEMEM
* DISCONTIGMEM model handled discontiguous physical memory and support NUMA
architectures.
* It introduced the notion of a memory "node" which is the basis of NUMA
memory management.
* `struct pglist_data` with `typedef pg_data_t` represents the node and
contains the node local array `mem_map`.
* This model is now deprecated to use SPARSEMEM which is efficient and
supports advanced physical memory features such as hot-plug and hot-remove.
---
* SPARSEMEM model abstracts the use of discontiguous memory as a collection of
sections.
* `struct mem_section` represents a section and logically points to an array
of `struct page` elements.
_Physical memory has limited size and managing it varies across hardware._
_Virtual memory makes the system appear to have more memory than available by
sharing among the processes._
---
Virtual Memory
--------------
* Virtual address must translate into physical address.
* Virtual memory size on a 32 bit system is 2^32 = 4GB and on 64 bit systems
2^64 a large number.
* With virtual memory all user space processes get consistent memory across
platforms and devices.
* Kernel allows protected and controlled access to physical memory.
_How is virtual memory allocated to user space processes?_
---
System calls
------------
Use space virtual memory allocation system calls.
### `brk ()` and `sbrk ()`
* `brk ()` takes an initial _address_ and sets it as _program break_.
* `sbrk ()` takes an _increment_ value and adds it to the _program break_.
* Increasing the _program break_ allocates memory to the process.
* Decreasing the _program break_ recovers memory from the process.
---
### `mmap ()`
* `mmap ()` creates a mapping in the process virtual address space and
returns its address.
* It takes a _start_ address, _length_ of the mapping, _protection_ and flags
to control the mapping.
* This is mainly used when allocating a large block of memory.
_These system calls are not called directly in user space as it requires
“managing” the memory._
_`malloc()` system library API provides memory management facility._
---
References
----------
* [Linux memory allocator :: Mani Kumar][1]
* [Physical Memory Model][2]
* [Memory: the flat, the discontiguous, and the sparse][3]
* [sparsemem memory model][4]
* `man: brk(2), mmap(2), malloc(3)`
[1]: https://manid2.gitlab.io/posts/linux-memory-allocator/
[2]: https://www.kernel.org/doc/html/latest/mm/memory-model.html
[3]: https://lwn.net/Articles/789304/
[4]: https://lwn.net/Articles/134804/