I realized if I have to write more about my work, I’ll have to throw around a lot of jargon and it’s not really fun if you haven’t yet had proper introduction to memory management terms or it’s been a while and you have trouble recollecting them. This post talks very briefly about some of the most frequently used terms in Linux memory management. I encourage you to read more about whatever topic you might be a stranger to. I intend to keep updating this post. So the current list is not complete by any means (I don’t think it can ever be).
These are the basic units of memory management in Linux. The sizes of pages may vary with architecture. 4 KB pages seem to be common in most 32-bit architectures. Larger page sizes (8 KB, 16 KB, etc) are more common in 64-bit architectures.
When configured, Linux also supports Huge pages, which are much larger pages.
The size of the huge pages on a system can be obtained using the command
$ cat /proc/meminfo | grep Hugepagesize
$ getconf PAGE_SIZE
should give the size of regular memory pages.
This is what memory management folk fondly refer to as ‘The VM’. It is a technique used by operating systems wherein the memory addresses used by processes are translated from a virtual address space to a physical address space by the MMU.
Since the addresses used are virtual, a process can run under the impression that it has way more memory than physically available, as the system can keep only what is currently required in the physical memory and bring in the rest later.
Another important benefit is protection of the system. Each process has its own virtual address space and cannot affect another process’s address space unless some sort of sharing is established.
Linux uses Demand Paging, which is a technique which allows the system to postpone the allocation of pages as long as possible. For example, when a process is executed with only a portion of its executable file in RAM, a page fault occurs when it tries to access what has not been brought to memory. The required pages are loaded on demand from the disk. Similarly, when huge files are accessed, only parts of them are kept in memory and the rest of the parts are loaded only when required.
Another kind of paging is called Anticipatory Paging, which is sort of the opposite of this. Here, pages are brought to memory well in advance in the hope of minimizing page faults.
Non Uniform Memory Access or NUMA
When there are multiple CPUs in a system, it is possible that some banks of memory are closer to some CPUs than the rest. In such cases, the memory closer to a CPU can be accessed much faster and significant delays may be encountered when memory is far away, especially in large systems. Such systems are called NUMA systems.
Uniform Memory Access or UMA
Here, all processors share the physical memory uniformly. There are no differences in the memory access times of different processors.
Each bank of memory used in a system is called a node. In NUMA systems, there are multiple nodes. When memory allocations happen in NUMA systems, the node closest to the running CPU is considered for allocation of pages.
Each node is divided into zones. These zones are divided based on their uses. A quick look at the enum zone_type in include/linux/mmzone.h shows that there can be up to 6 zones depending on the configuration –
ZONE_DMA For Direct Memory Accesses
ZONE_DMA32 Needed by x86_64
ZONE_NORMAL Normal addressable memory (DMA possible)
The kernel tries to allocate memory in the preferred zone. If no memory is available in that zone, fallback zones are considered in the order of priority.
In the Linux kernel, memory pages are allocated in powers of 2. The integer to which 2 is raised is called the order. For example, when a single page is requested, it is considered a zero order allocation.
Buddy Allocation/ Binary Buddy Allocation
The linux kernel memory allocator is called the Buddy Allocator. Memory is divided into several blocks. The number of pages in each block is raised to an integer (ranging from zero to MAX_ORDER, defined in the kernel) i.e, 1, 2, 4, 8 and so on are possible block sizes. If allocation of a certain block size cannot be fulfilled, higher order blocks are divided in half. These two halves are called buddies. This division continues till the desired block size is obtained and allocation is made. When the pages allocated are finally freed, the buddies are coalesced if they are both free.
If you are interested in seeing how the blocks are currently organized, try the following command:
$ cat /proc/buddyinfo
It will give you the number of free blocks for all the orders starting from 0 in ascending order, for all the nodes and zones.
I’ll be back soon 🙂